The Hall-Condition Index of a Graph and the Overfull Conjecture

Abstract

Let $s^{\prime }(G)$ denote the Hall-condition index of a graph $G$. Hilton and Johnson recently introduced this parameter and proved that $\mathrm{\Delta }(G)\le s^{\prime }(G)\le \mathrm{\Delta }(G)+1$. A graph $G$ is $s^{\prime }$-Class 1 if $s^{\prime }(G)=\mathrm{\Delta }(G)$ and is $s^{\prime }$-Class 2 otherwise. A graph $G$ is $s^{\prime }$-critical if $G$ is connected, $s^{\prime }$-Class 2, and, for every edge $e$, $s^{\prime }(G–e)<s^{\prime }(G)$. We use the concept of the fractional chromatic index of a graph to classify $s^{\prime }$-Class 2 in terms of overfull subgraphs, and similarly to classify $s^{\prime }$-critical graphs. We apply these results to show that the following variation of the Overfull Conjecture is true;

A graph $G$ is $s^{\prime }$-Class 2 if and only if $G$ contains an overfull subgraph $H$ with $\mathrm{\Delta }(G)=\mathrm{\Delta }(H)$.