The Hall-Condition Number of a Graph

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].