The overfullness of graphs with small minimum degree and large maximum degree

Abstract

Given a simple graph $G$, denote by $\Delta (G)$, $\delta (G)$, and ${\chi }^{\prime }(G)$ the maximum degree, the minimum degree, and the chromatic index of $G$, respectively. We say $G$ is \emph{$\Delta$-critical} if ${\chi }^{\prime }(G)=\Delta (G)+1$ and ${\chi }^{\prime }(H)\le \Delta (G)$ for every proper subgraph $H$ of $G$; and $G$ is \emph{overfull} if $|E(G)|>\Delta \lfloor |V(G)|/2\rfloor$. Since a maximum matching in $G$ can have size at most $\lfloor |V(G)|/2\rfloor$, it follows that ${\chi }^{\prime }(G)=\Delta (G)+1$ if $G$ is overfull. Conversely, let $G$ be a $\Delta$-critical graph. The well known overfull conjecture of Chetwynd and Hilton asserts that $G$ is overfull provided $\Delta (G)>|V(G)|/3$. In this paper, we show that any $\Delta$-critical graph $G$ is overfull if $\Delta (G)-7\delta (G)/4\ge (3|V(G)|-17)/4$.

One portion of arXiv:2005.12909 is incorporated into this paper. arXiv admin note: text overlap with arXiv:2004.00734, arXiv:2103.05171