The Hall-Condition Number of a Graph

Abstract

The Hall-condition number $s(G)$ of a graph $G$ is defined and some of its fundamental properties are derived. This parameter, introduced in [6], bears a certain relation to the chromatic number $\chi (G)$ and the choice number $c(G)$ (see [3] and [7]).

One result here, that $\chi (G)–s(G)$ may be arbitrarily large, solves a problem posed in [6].