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.展开更多
LetGbe a planar graph with maximum degreeΔ.In this paper,we prove that if any4-cycle is not adjacent to ani-cycle for anyi∈{3,4}in G,then the list edge chromatic numberχl（G）=Δand the list total chromatic number...LetGbe a planar graph with maximum degreeΔ.In this paper,we prove that if any4-cycle is not adjacent to ani-cycle for anyi∈{3,4}in G,then the list edge chromatic numberχl（G）=Δand the list total chromatic numberχl（G）=Δ＋1.展开更多
Suppose that G is a planar graph with maximum degree △. In this paper it is proved that G is total-（△ ＋ 2）-choosable if （1） △ ≥ 7 and G has no adjacent triangles （i.e., no two triangles are incident with a c...Suppose that G is a planar graph with maximum degree △. In this paper it is proved that G is total-（△ ＋ 2）-choosable if （1） △ ≥ 7 and G has no adjacent triangles （i.e., no two triangles are incident with a common edge）; or （2） △ ≥6 and G has no intersecting triangles （i.e., no two triangles are incident with a common vertex）; or （3） △ ≥ 5, G has no adjacent triangles and G has no k-cycles for some integer k ∈ {5, 6}.展开更多
针对符号图的列表点染色问题,证明了任何不含K_5-子式或K_(3,3)-子式的符号图的选择数至多为5,并且此处的上界5是不可再降低的,从而推广了Jin、Kang与Steffen发表于"European Journal of Combinatorics,2016,52:234-243"的关...针对符号图的列表点染色问题,证明了任何不含K_5-子式或K_(3,3)-子式的符号图的选择数至多为5,并且此处的上界5是不可再降低的,从而推广了Jin、Kang与Steffen发表于"European Journal of Combinatorics,2016,52:234-243"的关于符号平面图的对应结论。展开更多
基金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.
基金Supported by National Natural Science Foundation of China(Grant Nos.11201440 and 11271006)Graduate Independent Innovation Foundation of Shandong University(Grant No.yzc12100)
文摘LetGbe a planar graph with maximum degreeΔ.In this paper,we prove that if any4-cycle is not adjacent to ani-cycle for anyi∈{3,4}in G,then the list edge chromatic numberχl（G）=Δand the list total chromatic numberχl（G）=Δ＋1.
文摘Suppose that G is a planar graph with maximum degree △. In this paper it is proved that G is total-（△ ＋ 2）-choosable if （1） △ ≥ 7 and G has no adjacent triangles （i.e., no two triangles are incident with a common edge）; or （2） △ ≥6 and G has no intersecting triangles （i.e., no two triangles are incident with a common vertex）; or （3） △ ≥ 5, G has no adjacent triangles and G has no k-cycles for some integer k ∈ {5, 6}.
文摘针对符号图的列表点染色问题,证明了任何不含K_5-子式或K_(3,3)-子式的符号图的选择数至多为5,并且此处的上界5是不可再降低的,从而推广了Jin、Kang与Steffen发表于"European Journal of Combinatorics,2016,52:234-243"的关于符号平面图的对应结论。
