A star k-edge-coloring is a proper k-edge-coloring such that every connected bicolored subgraph is a path of length at most 3.The star chromatic indexχ'_(st)(G)of a graph G is the smallest integer k such that G h...A star k-edge-coloring is a proper k-edge-coloring such that every connected bicolored subgraph is a path of length at most 3.The star chromatic indexχ'_(st)(G)of a graph G is the smallest integer k such that G has a star k-edge-coloring.The list star chromatic index ch'st(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 constant c(ε)such that if mad(G)<8/3-ε,then■and the coefficient 3/2 ofΔis the best possible.The proof applies a newly developed coloring extension method by assigning color sets with different sizes.展开更多
基金supported by National Natural Science Foundation of China(Grant No.11901318)the Fundamental Research Funds for the Central Universities,Nankai University(Grant No.63191425)supported by National Natural Science Foundation of China(Grant Nos.11571149 and 11971205)
文摘A star k-edge-coloring is a proper k-edge-coloring such that every connected bicolored subgraph is a path of length at most 3.The star chromatic indexχ'_(st)(G)of a graph G is the smallest integer k such that G has a star k-edge-coloring.The list star chromatic index ch'st(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 constant c(ε)such that if mad(G)<8/3-ε,then■and the coefficient 3/2 ofΔis the best possible.The proof applies a newly developed coloring extension method by assigning color sets with different sizes.
