Informace o publikaci
Classes of graphs with small rank decompositions are chi-bounded
| Autoři | |
|---|---|
| Rok publikování | 2012 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | European Journal of Combinatorics |
| Citace | |
| Doi | http://dx.doi.org/10.1016/j.ejc.2011.12.005 |
| Popis | 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. |