Paper Info
Title
On the average degree of edge chromatic critical graphs
Abstract
Let G be a simple graph, and let χ′(G) and Δ(G) denote the chromatic index and the maximum degree of G, respectively. A graph G is a critical class two graph if χ′(G)=Δ(G)+1 and χ′(H)≤Δ(G) for every proper subgraph H of G. Let d‾(G) denote the average degree of G, i.e., d‾(G)=2|E(G)|/|V(G)|. Vizing in 1968 conjectured that d‾(G)≥Δ(G)−1+3/n if G is a critical class two graph of order n. In this paper, we prove that d‾(G)≥34Δ(G)−8 if G is a critical class two graph. Let δ(G) denote the minimum degree of G. We show that there exist two functions D and D0 such that for any ϵ∈(0,1), if G is a critical class two graph with Δ(G)≥D(ϵ) and δ(G)≥D0(ϵ), then d‾(G)≥(1−ϵ)Δ(G). We will give two specific functions satisfying the statement above in the paper. Moreover, we show that if G is a critical class two graph and δ(G)≥(log⁡Δ(G))34, then d‾(G)≥Δ(G)−o(Δ(G)).
Year
DOI
Venue
2021
10.1016/j.jctb.2020.04.004
Journal of Combinatorial Theory, Series B
Keywords
DocType
Volume
Edge coloring,Critical class two graphs,Vizing's average degree conjecture
Journal
147
ISSN
Citations 
PageRank 
0095-8956
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Yan Cao1144.30
Guantao Chen210725.00