Cookies

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

Profile

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

Abstract

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.