Upper Bounds on List Star Chromatic Index of Sparse Graphs
Upper Bounds on List Star Chromatic Index of Sparse Graphs
复制标题
DOI：
10.1007/s10114-019-8546-7
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Jia Li;Katherine M. Horacek;Rong Luo;Z. Miao
中科院分区：
文献类型：
--
作者：
Jia Li;Katherine M. Horacek;Rong Luo;Z. Miao
星形k-边染色是一种特殊的边染色，使得每一个连通的双色子图都是一条长度不超过3的路。图G的星星色数（G）是使G具有纯边染色的最小整数。列表星星色指数（G）也类似地定义。星星边着色问题是NP-完全的，而且由于完全图的星星色指数是线性还是超线性的未知数，使得得到严格的上界更加困难.在本文中，我们研究，相比之下，最好的线性上界稀疏图类。我们证明了对每一个ε> 0，存在一个常数tc（ε），使得当mad（G）<时，（G）≤且Δ的系数是最佳可能的.证明应用了一种新的着色扩展方法，通过分配不同大小的颜色集。
Astar k-edge-coloringis a properk-edge-coloring such that every connected bicolored subgraph is a path of length at most 3. The star chromatic index(G) of a graphGis the smallest integerksuch thatGhas a stark-edge-coloring. The list star chromatic index(G) is defined analogously. The star edge coloring problem is known to be NP-complete, and it is even hard to obtain tight upper bound as it is unknown whether the star chromatic index for complete graph is linear or super linear. In this paper, we study, in contrast, the best linear upper bound for sparse graph classes. We show that for everyε> 0 there exists a constantc(ε) such that if mad(G) <, then(G) ≤and the coefficientof Δ is the best possible. The proof applies a newly developed coloring extension method by assigning color sets with different sizes.