Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102449
Title: Happy edges: Threshold-coloring of regular lattices
Authors: Alam, Md. J.
Kobourov, S. G.
Pupyrev, S.
Toeniskoetter, J.
Issue Date: 2014
Publisher: Springer Verlag
Citation: Happy edges: Threshold-coloring of regular lattices / Md. J. Alam, S. G. Kobourov, S. Pupyrev, et al. — DOI 10.1007/978-3-319-07890-8_3 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2014. — Vol. 8496 LNCS. — P. 28-39.
Abstract: We study a graph coloring problem motivated by a fun Sudoku-style puzzle. Given a bipartition of the edges of a graph into near and far sets and an integer threshold t, a threshold-coloring of the graph is an assignment of integers to the vertices so that endpoints of near edges differ by t or less, while endpoints of far edges differ by more than t. We study threshold-coloring of tilings of the plane by regular polygons, known as Archimedean lattices, and their duals, the Laves lattices. We prove that some are threshold-colorable with constant number of colors for any edge labeling, some require an unbounded number of colors for specific labelings, and some are not threshold-colorable. © 2014 Springer International Publishing.
Keywords: ARTIFICIAL INTELLIGENCE
COMPUTER SCIENCE
COMPUTERS
BIPARTITION
EDGE LABELING
GRAPH COLORING PROBLEM
LABELINGS
REGULAR LATTICE
REGULAR POLYGON
GRAPH THEORY
URI: http://hdl.handle.net/10995/102449
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84903746702
PURE ID: 370555
39ac752f-d301-4c07-8bfc-28486af6164a
ISSN: 3029743
ISBN: 9783319078892
DOI: 10.1007/978-3-319-07890-8_3
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84903746702.pdf1,17 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.