Premium
A note on the bichromatic numbers of graphs
Author(s) -
Epple Dennis D. A.,
Huang Jing
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20479
Subject(s) - combinatorics , mathematics , induced subgraph , graph , bounded function , cograph , chordal graph , discrete mathematics , clique number , upper and lower bounds , 1 planar graph , vertex (graph theory) , mathematical analysis
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