Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102488
Title: Threshold-coloring and unit-cube contact representation of graphs
Authors: Alam, Md. J.
Chaplick, S.
Fijavž, G.
Kaufmann, M.
Kobourov, S. G.
Pupyrev, S.
Issue Date: 2013
Publisher: Springer Verlag
Citation: Threshold-coloring and unit-cube contact representation of graphs / Md. J. Alam, S. Chaplick, G. Fijavž, et al. — DOI 10.1007/978-3-642-45043-3_4 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2013. — Vol. 8165 LNCS. — P. 26-37.
Abstract: We study threshold coloring of graphs where the vertex colors, represented by integers, describe any spanning subgraph of the given graph as follows. Pairs of vertices with near colors imply the edge between them is present and pairs of vertices with far colors imply the edge is absent. Not all planar graphs are threshold-colorable, but several subclasses, such as trees, some planar grids, and planar graphs with no short cycles can always be threshold-colored. Using these results we obtain unit-cube contact representation of several subclasses of planar graphs. We show the NP-completeness for two variants of the threshold coloring problem and describe a polynomial-time algorithm for another. © 2013 Springer-Verlag.
Keywords: ALGORITHMS
COLOR
COMPUTER SCIENCE
GRAPHIC METHODS
COLORING PROBLEMS
NP-COMPLETENESS
PLANAR GRAPH
PLANAR GRIDS
POLYNOMIAL-TIME ALGORITHMS
REPRESENTATION OF GRAPHS
SHORT CYCLE
SUBGRAPHS
GRAPH THEORY
URI: http://hdl.handle.net/10995/102488
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84893032513
PURE ID: 880694
1be444f8-8402-4aca-890d-3ca75524818e
ISSN: 3029743
ISBN: 9783642450426
DOI: 10.1007/978-3-642-45043-3_4
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84893032513.pdf387,2 kBAdobe PDFView/Open


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