We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Publication details for Professor Matthew Johnson

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

Author(s) from Durham


Hall's condition is a simple condition that a graph G and list assignment L must satisfy if G has a proper L-colouring. The Hall number of G is the smallest integer m such that whenever each list has size 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 characterize graphs with Hall number 2.