Publication details

Classes of graphs with small rank decompositions are chi-bounded



Year of publication 2012
Type Article in Periodical
Magazine / Source European Journal of Combinatorics
Description A class of graphs g is chi-bounded if the chromatic number of graphs in g. is bounded by a function of the clique number. We show that if a class g is chi-bounded, then every class of graphs admitting a decomposition along cuts of small rank to graphs from g is chi-bounded. As a corollary, we obtain that every class of graphs with bounded rank-width (or equivalently, clique-width) is chi-bounded. (C) 2012 Elsevier Ltd. All rights reserved.

You are running an old browser version. We recommend updating your browser to its latest version.

More info