The Relationship Between an Edge Colouring Conjecture and A Total Colouring Conjecture

Abstract

Chetwynd and Hilton made the following $edge-colouringconjecture$: if a simple graph $G$ satisfies $\mathrm{\Delta }(G)>\frac{1}{3}|V(G)|$, then $G$ is Class $2$ if and only if it contains an overfull subgraph $H$ with $\mathrm{\Delta }(H)=\mathrm{\Delta }(G)$. They also made the following $total-colouringconjecture$: if a simple graph $G$ satisfies $\mathrm{\Delta }(G)\ge \frac{1}{2}(|V(G)|+1)$, then $G$ is Type $2$ if and only if $G$ contains a non-conformable subgraph $H$ with $\mathrm{\Delta }(H)=\mathrm{\Delta }(G)$. Here we show that if the edge-colouring conjecture is true for graphs of even order satisfying $\mathrm{\Delta }(G)>\frac{1}{2}|V(G)|$, then the total-colouring conjecture is true for graphs of odd order satisfying $\delta (G)\ge \frac{3}{4}|V(G)|–\frac{1}{4}$ and $\text{def}(G)\ge 2(\mathrm{\Delta }(G)–\delta (G)+1)$.