Skip to main content

Research Repository

Advanced Search

Characterization of graphs with Hall number 2

Eslachi, Ch; Johnson, Matthew


Ch Eslachi


Hall's condition is a simple requirement that a graph G and list assignment L must satisfy if G is to have a proper L-colouring. The Hall number of G is the smallest integer m such that whenever the lists on the vertices each has size at least m and Hall's condition is satisfied a proper L-colouring exists. Hilton and P.D. Johnson introduced the parameter and showed that a graph has Hall number 1 if and only if every block is a clique. In this paper we give a forbidden-induced-subgraph characterization of graphs with Hall number 2.


Eslachi, C., & Johnson, M. (2004). Characterization of graphs with Hall number 2. Journal of Graph Theory, 45(2), 81-100.

Journal Article Type Article
Publication Date Feb 1, 2004
Deposit Date Oct 7, 2008
Journal Journal of Graph Theory
Print ISSN 0364-9024
Electronic ISSN 1097-0118
Publisher Wiley
Peer Reviewed Peer Reviewed
Volume 45
Issue 2
Pages 81-100
Keywords List coloring, Hall number, Choice number, Chromatic number.
Publisher URL