Brooks-type Theorems For Pair-list Colorings And List Homomorphisms

摘要

Brooks proved that every connected graph other than a clique or odd cycle can be colored with △ colors. Erdos, Rubin, and Taylor (and, independently, Vizing) generalized the theorem of Brooks to list colorings, describing all uncolorable connected graphs in which no vertex has a list smaller than its degree. Other authors have extended this to list T-colorings and their generalizations. We further extend it to model pair-list colorings. In addition to including all of the previous situations, pair-list colorings also generalize list homomorphisms (also known as list H-colorings). In the general context of pair-list colorings, we prove a Brooks-type theorem which extends many (but not all) of the existing results. Our result applies to both graphs and digraphs, with or without loops. We discuss several applications of the result, including a polynomial test for the existence of balanced list homomorphisms and retractions.