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