Complexity of conditional colorability of graphs

详细信息    查看全文

• 作者：Xueliang Li ; Xiangmei Yao ; Wenli Zhou ; Hajo Broersma
• 关键词：Vertex coloring ; Conditional coloring ; (Conditional) chromatic number ; Algorithm ; Complexity ; NP-complete
• 刊名：Applied Mathematics Letters
• 出版年：2009
• 出版时间：March 2009
• 年：2009
• 卷：22
• 期：3
• 页码：320-324
• 全文大小：400 K

文摘

For positive integers k and r, a conditional (k,r)-coloring of a graph G is a proper k-coloring of the vertices of G such that every vertex v of degree d(v) in G is adjacent to vertices with at least min{r,d(v)} different colors. The smallest integer k for which a graph G has a conditional (k,r)-coloring is called the rth-order conditional chromatic number, and is denoted by χ_r(G). It is easy to see that conditional coloring is a generalization of traditional vertex coloring (the case r=1). In this work, we consider the complexity of the conditional colorability of graphs. Our main result is that conditional (3,2)-colorability remains NP-complete when restricted to planar bipartite graphs with maximum degree at most 3 and arbitrarily high girth. This differs considerably from the well-known result that traditional 3-colorability is polynomially solvable for graphs with maximum degree at most 3. On the other hand we show that (3,2)-colorability is polynomially solvable for graphs with bounded tree-width. We also prove that some other well-known complexity results for traditional coloring still hold for conditional coloring.