Overfullness of critical class 2 graphs with a small core degree

2020/08/18 by Cao, Yan, Chen, Guantao, Shan, Songling
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2008.08135

Abstract

Let G be a simple graph, and let n, Δ(G) and χ' (G) be the order, the maximum degree and the chromatic index of G, respectively. We call G overfull if |E(G)|/\lfloor n/2\rfloor > Δ(G), and critical if χ'(H) < χ'(G) for every proper subgraph H of G. Clearly, if G is overfull then χ'(G) = Δ(G)+1. The core of G, denoted by G_Δ, is the subgraph of G induced by all its maximum degree vertices. Hilton and Zhao conjectured that for any critical class 2 graph G with Δ(G) ≥ 4, if the maximum degree of G_Δ is at most two, then G is overfull, which in turn gives Δ(G) > n/2 +1. We show that for any critical class 2 graph G, if the minimum degree of G_Δ is at most two and Δ(G) > n/2 +1, then G is overfull.

Related

• Overfullness of edge-critical graphs with small minimal core degree
• Δ-critical graphs with a vertex of degree 2
• The overfullness of graphs with small minimum degree and large maximum degree
• The Core Conjecture of Hilton and Zhao II: a Proof
• A new improvement to the Overfull Conjecture