Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/90255
Title: Threshold-coloring and unit-cube contact representation of planar graphs
Authors: Alam, M. J.
Chaplick, S.
Fijavž, G.
Kaufmann, M.
Kobourov, S. G.
Pupyrev, S.
Toeniskoetter, J.
Issue Date: 2017
Publisher: Elsevier B.V.
Citation: Threshold-coloring and unit-cube contact representation of planar graphs / M. J. Alam, S. Chaplick, G. Fijavž, M. Kaufmann, et al. . — DOI 10.1016/j.dam.2015.09.003 // Discrete Applied Mathematics. — 2017. — Iss. 216. — P. 2-14.
Abstract: In this paper we study threshold-coloring of graphs, where the vertex colors represented by integers are used to describe any spanning subgraph of the given graph as follows. A pair of vertices with a small difference in their colors implies that the edge between them is present, while a pair of vertices with a big color difference implies that 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. Variants of the threshold-coloring problem are related to well-known graph coloring and other graph-theoretic problems. Using these relations we show the NP-completeness for two of these variants, and describe a polynomial-time algorithm for another. © 2015 Elsevier B.V.
Keywords: GRAPH COLORING
PLANAR GRAPHS
THRESHOLD-COLORING
UNIT-CUBE CONTACT REPRESENTATION
ALGORITHMS
COLOR
COLORIMETRY
COLORING
GEOMETRY
GRAPHIC METHODS
POLYNOMIAL APPROXIMATION
TREES (MATHEMATICS)
COLOR DIFFERENCE
COLORING PROBLEMS
GRAPH COLORINGS
GRAPH-THEORETIC PROBLEM
NP-COMPLETENESS
PLANAR GRAPH
POLYNOMIAL-TIME ALGORITHMS
UNIT-CUBE CONTACT REPRESENTATION
GRAPH THEORY
URI: http://hdl.handle.net/10995/90255
https://elar.urfu.ru/handle/10995/90255
Access: info:eu-repo/semantics/openAccess
elsevier-specific: oa user license
SCOPUS ID: 84950145059
WOS ID: 000390504000002
PURE ID: 1309638
ISSN: 0166-218X
DOI: 10.1016/j.dam.2015.09.003
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
10.1016-j.dam.2015.09.003.pdf516,65 kBAdobe PDFView/Open


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