A note on the bichromatic numbers of graphs

For a pair of integers k, l≥0, a graph G is (k, l)‐colorable if its vertices can be partitioned into at most k independent sets and at most l cliques. The bichromatic number χ^b(G) of G is the least integer r such that for all k, l with k+l=r, G is (k, l)‐colorable. The concept of bichromatic numbers simultaneously generalizes the chromatic number χ(G) and the clique covering number θ(G), and is important in studying the speed of hereditary properties and edit distances of graphs. It is easy to see that for every graph G the bichromatic number χ^b(G) is bounded above by χ(G)+θ(G)?1. In this article, we characterize all graphs G for which the upper bound is attained, i.e., χ^b(G)=χ(G)+θ(G)?1. It turns out that all these graphs are cographs and in fact they are the critical graphs with respect to the (k, l)‐colorability of cographs. More specifically, we show that a cograph H is not (k, l)‐colorable if and only if H contains an induced subgraph G with χ(G)=k+1, θ(G)=l+1 and χ^b(G)=k+l+1. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 263–269, 2010