2021/08/08 by Cao, Yan, Chen, Guantao, Jing, Guangming +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2108.03549
A simple graph G with maximum degree Δ is overfull if |E(G)|>Δ\lfloor |V(G)|/2\rfloor. The core of G, denoted GΔ, is the subgraph of G induced by its vertices of degree Δ. Clearly, the chromatic index of G equals Δ+1 if G is overfull. Conversely, Hilton and Zhao in 1996 conjectured that if G is a simple connected graph with Δ≥ 3 and Δ(GΔ)≤ 2, then χ'(G)=Δ+1 implies that G is overfull or G=P^*, where P^* is obtained from the Petersen graph by deleting a vertex (Core Conjecture). The goal of this paper is to develop the concepts of ``pseudo-multifan'' and ``lollipop'' and study their properties in an edge colored graph. These concepts turn out to be powerful tools in edge coloring graphs with a small core degree.