A star coloring of an undirected graph G is a proper coloring of G such that no path of length 3 in G is bicolored. The star chromatic number of an undirected graph G, denoted by xs（G）, is the smallest integer k for...A star coloring of an undirected graph G is a proper coloring of G such that no path of length 3 in G is bicolored. The star chromatic number of an undirected graph G, denoted by xs（G）, is the smallest integer k for which G admits a star coloring with k colors. In this paper, we show that if G is a graph with maximum degree A, then xs（G） ≤ [7△3/2]], which gets better bound than those of Fertin, Raspaud and Reed.展开更多
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 the Natural Science Foundation of Chongqing Science and Technology Commission (Grant No.2007BB2123)
文摘A star coloring of an undirected graph G is a proper coloring of G such that no path of length 3 in G is bicolored. The star chromatic number of an undirected graph G, denoted by xs（G）, is the smallest integer k for which G admits a star coloring with k colors. In this paper, we show that if G is a graph with maximum degree A, then xs（G） ≤ [7△3/2]], which gets better bound than those of Fertin, Raspaud and Reed.
基金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.
