A Brooks‐Type Theorem for the Bichromatic Number
Dennis D. A. Epple, Jing Huang · Journal of Graph Theory · 2014
Abstract 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. In this article, we prove a theorem, akin to that of Brooks, which states that every graph G has its bichromatic number less than or equal to its bidegree , unless G belongs to a set of specified graphs in which case is equal to .