2021/03/09 by Yan Cao, Guantao Chen, Cao, Yan +3
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2103.05171
openalex publication_date 2021/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a simple graph G, denote by n, Δ(G), and χ'(G) its order, maximum degree, and chromatic index, respectively. A connected class 2 graph G is edge-chromatic critical if χ'(G-e)Δ(G) \lfloor n/2 \rfloor. Clearly, overfull graphs are class 2 and any graph obtained from a regular graph of even order by splitting a vertex is overfull. Let G be an n-vertex connected regular class 1 graph with Δ(G) >n/3. Hilton and Zhao in 1997 conjectured that if G^* is obtained from G by splitting one vertex of G into two vertices, then G^* is edge-chromatic critical, and they verified the conjecture for graphs G with Δ(G)≥ (n)/(2)(√(7)-1)≈ 0.82n. The graph G^* is easily verified to be overfull, and so the hardness of the conjecture lies in showing that the deletion of every of its edge decreases the chromatic index. Except in 2002, Song showed that the conjecture is true for a special class of graphs G with Δ(G)≥ (n)/(2), no other progress on this conjecture had been made. In this paper, we confirm the conjecture for graphs G with Δ(G) ≥ 0.75n.