Lambda-backbone Colorings along Pairwise Disjoint Stars and Matchings
Lambda-backbone Colorings along Pairwise Disjoint Stars and Matchings
复制标题
DOI：
10.1016/j.disc.2008.04.007
复制
发表时间：
2009-09
期刊：
影响因子：
--
通讯作者：
H. J. Broersma;J. Fujisawa;B. Marchal;D. Paulusma;A. Salman;Kiyoshi Yoshimoto
中科院分区：
文献类型：
--
作者：
H. J. Broersma;J. Fujisawa;B. Marchal;D. Paulusma;A. Salman;Kiyoshi Yoshimoto
给定一个整数λ≥2，一个图G=(V，E)和G(G的主干)的一个支撑子图H，(G，H)的一个λ-主干染色是V→{1，2，…，其中分配给H中相邻顶点的颜色至少相差λ。我们研究的情况是，主干要么是两两不相交的恒星的集合，要么是匹配的。证明了对于G的一个星骨干S，(G，S)的一个ℓ-骨干着色的最小个数λ在{1，…，ℓ}eXist与色数−(G)的乘法因子最多相差2λ1χ(G)。对于匹配主干的特殊情况，这个因子大约为2−2λ+1。我们还证明了问题的计算复杂性：给定一个具有星形主干S且整数ℓ的图G，是否存在(G，S)的λ-主干着色，其颜色在{1，…，ℓ}？“在ℓ=λ+1和ℓ=λ+2之间从多项式可解跳到NP-完全(对于匹配，ℓ=λ+2甚至是NP-完全的)。最后，我们讨论了一些关于平面图的公开问题。
Given an integer λ≥2, a graph G=(V,E) and a spanning subgraph H of G (the backbone of G), a λ-backbone coloring of (G,H) is a proper vertex coloring V→{1,2,…} of G, in which the colors assigned to adjacent vertices in H differ by at least λ. We study the case where the backbone is either a collection of pairwise disjoint stars or a matching. We show that for a star backbone S of G the minimum number ℓ for which a λ-backbone coloring of (G,S) with colors in {1,…,ℓ} exists can roughly differ by a multiplicative factor of at most 2−1λ from the chromatic number χ(G). For the special case of matching backbones this factor is roughly 2−2λ+1. We also show that the computational complexity of the problem “Given a graph G with a star backbone S, and an integer ℓ, is there a λ-backbone coloring of (G,S) with colors in {1,…,ℓ}?” jumps from polynomially solvable to NP-complete between ℓ=λ+1 and ℓ=λ+2 (the case ℓ=λ+2 is even NP-complete for matchings). We finish the paper by discussing some open problems regarding planar graphs.