Publication details
Classes of graphs with small rank decompositions are chi-bounded
| Authors | |
|---|---|
| Year of publication | 2012 |
| Type | Article in Periodical |
| Magazine / Source | European Journal of Combinatorics |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.ejc.2011.12.005 |
| 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. |