Skip to main content

Research Repository

Advanced Search

Characterization of graphs with Hall number 2

Eslachi, Ch; Johnson, Matthew

Authors

Ch Eslachi



Abstract

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.

Citation

Eslachi, C., & Johnson, M. (2004). Characterization of graphs with Hall number 2. Journal of Graph Theory, 45(2), 81-100. https://doi.org/10.1002/jgt.10154

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
DOI https://doi.org/10.1002/jgt.10154
Keywords List coloring, Hall number, Choice number, Chromatic number.
Publisher URL http://www3.interscience.wiley.com/cgi-bin/abstract/106571506/ABSTRACT


You might also like



Downloadable Citations