Classes of graphs with small rank decompositions are chi-bounded

DVORAK, Z a Daniel KRÁĽ. Classes of graphs with small rank decompositions are chi-bounded. European Journal of Combinatorics. LONDON: ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2012, roč. 33, č. 4, s. 679-683. ISSN 0195-6698. Dostupné z: https://doi.org/10.1016/j.ejc.2011.12.005.

Základní údaje

Originální název

Classes of graphs with small rank decompositions are chi-bounded

Autoři

DVORAK, Z a Daniel KRÁĽ

Vydání

European Journal of Combinatorics, LONDON, ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2012, 0195-6698

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.658

Označené pro přenos do RIV

Ne

DOI

https://doi.org/10.1016/j.ejc.2011.12.005

UT WoS

000300740600024

---

Anotace

V originále

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.