Given a simple graph $G$, denote by $Delta(G)$, $delta(G)$, and $chi(G)$ the maximum degree, the minimum degree, and the chromatic index of $G$, respectively. We say $G$ is emph{$Delta$-critical} if $chi(G)=Delta(G)+1$ and $chi(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(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) - 7delta(G)/4ge(3|V(G)|-17)/4$.
Download