2020/05/25 by Yan Cao, Guantao Chen, Cao, Yan +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2005.12909
Let G be a simple graph with maximum degree Δ. A classic result of Vizing shows that χ'(G), the chromatic index of G, is either Δ or Δ+1. We say G is of Class 1 if χ'(G)=Δ, and is of Class 2 otherwise. A graph G is Δ-critical if χ'(G)=Δ+1 and χ'(H)Δ\lfloor (|V(G)|-1)/2 \rfloor. Clearly, overfull graphs are Class 2. Hilton and Zhao in 1997 conjectured that if G is obtained from an n-vertex Δ-regular Class 1 graph with maximum degree greater than n/3 by splitting a vertex, then being overfull is the only reason for G to be Class 2. This conjecture was only confirmed when Δ≥ (n)/(2)(√(7)-1)≈ 0.82n. In this paper, we improve the bound on Δ from (n)/(2)(√(7)-1) to 0.75n. Considering the structure of Δ-critical graphs with a vertex of degree 2, we also show that for an n-vertex Δ-critical graph with Δ≥ (3n)/(4), if it contains a vertex of degree 2, then it is overfull. We actually obtain a more general form of this result, which partially supports the overfull conjecture of Chetwynd and Hilton from 1986, which states that if G is an n-vertex Δ-critical graph with Δ>n/3, then G contains an overfull subgraph H with Δ(H)=Δ. Our proof techniques are new and might shed some light on attacking both of the conjectures when Δ is large.