SOFSEM 2007: Theory and Practice of Computer Science
SOFSEM 2007: Theory and Practice of Computer Science
复制标题
SOFSEM 2007：计算机科学的理论与实践
DOI：
10.1007/978-3-540-69507-3_15
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Broersma H
中科院分区：
文献类型：
--
作者：
Broersma H
我们继续研究骨干着色，在WG 2003中介绍的经典顶点着色的变化。给定一个图G =（V，E）和G的一个生成子图H（G的主干），G的λ-主干染色是V →{1，2，.}其中分配给H中相邻顶点的颜色至少相差λ。早期研究的主要结果是，这种coloringsV→{1，2，..}的颜色的最小数量在最坏的情况下，存在的最大值是一个因子乘以色数（对于所有研究类型的骨干）。我们在这里证明，对于分裂图和匹配或星星骨干，λ至多是一个小的加法常数（取决于λ）高于色数。尽管分裂图有一个很好的结构，但这些结果很难证明。我们的证明结合了联合收割机算法和组合参数。我们还表明，我们的结果意味着更好的上界比以前已知的界限上的其他图形类。
We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graphG= (V,E) and a spanning subgraphHofG(the backbone ofG), aλ-backbone coloring forGandHis a proper vertex coloringV→{1,2,...} ofGin which the colors assigned to adjacent vertices inHdiffer by at leastλ. The main outcome of earlier studies is that the minimum number ℓ of colors for which such coloringsV→{1,2,...,ℓ} exist in the worst case is a factor times the chromatic number (for all studied types of backbones). We show here that for split graphs and matching or star backbones, ℓ is at most a small additive constant (depending onλ) higher than the chromatic number. Despite the fact that split graphs have a nice structure, these results are difficult to prove. Our proofs combine algorithmic and combinatorial arguments. We also indicate other graph classes for which our results imply better upper bounds on ℓ than the previously known bounds.