Jing Huang

Brooks proved that every connected graph other than a clique or odd cycle can be coloured with $\Delta$ colours. Erd\"{o}s, Rubin, and Taylor (and independently Vizing) generalized the theorem of Brooks to list colourings, describing all uncolourable connected graphs in which the degree of a vertex never exceeds the size of its list. Other authors have extended this to list $T$-colourings and their generalizations. We further extend to model to pair-list colourings. In addition to including all of the previous situations, pair-list colourings also generalize list homomorphisms (also known as list $H$-colourings). In the general context of pair-list colourings, we prove a Brooks type theorem which extends many of the existing results. Our result applies to both graphs and digraphs, with or without loops. The work is joint with Feder and Hell.