Characterization of graphs with Hall number 2

Eslachi, Ch; Johnson, Matthew

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.
• Public URL: https://durham-repository.worktribe.com/output/1557286
• Publisher URL: http://www3.interscience.wiley.com/cgi-bin/abstract/106571506/ABSTRACT