Threshold-coloring and unit-cube contact representation of planar graphs

详细信息    查看全文

• 作者：Md. Jawaherul Alam^a ; Steven Chaplick^b ; Ga&scaron ; per Fijavž^d ; Michael Kaufmann^c ; Stephen G. Kobourov^a ; Sergey Pupyrev^a ; ^e ; Jackson Toeniskoetter^a ; ^{jacktoe@email.arizona.edu}
• 关键词：Graph coloring ; Threshold-coloring ; Planar graphs ; Unit-cube contact representation
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：216
• 期：part_P1
• 页码：2-14
• 全文大小：614 K
• 卷排序：216

文摘

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.