A Brooks-Type Theorem for the Bichromatic Number
A classical theorem of Brooks in graph coloring theory states that every connected graph G has its chromatic number less than or equal to its maximum degree , unless G is a complete graph or an odd cycle in which case is equal to . Brooks' theorem has been extended to list colorings by Erd?s, Rubin, and Taylor (and, independently, by Vizing) and to some of their variants such as list T-colorings and pair-list colorings. The bichromatic number is a relatively new parameter arisen in the study of extremal hereditary properties of graphs. This parameter simultaneously generalizes the chromatic number and the clique covering number of a graph.
bichromatic number brooks' theorem (k l)-colouring