Classes of graphs with small rank decompositions are \(\chi \)-bounded

DOI10.1016/j.ejc.2011.12.005zbMath1237.05072arXiv1107.2161OpenAlexW2003779279WikidataQ57601373 ScholiaQ57601373MaRDI QIDQ412260

Daniel Král', Zdeněk Dvořák

Publication date: 4 May 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1107.2161

zbMATH Keywords

chromatic numberclique numberbounded rank-widthchi-boundedclique width

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Rank-width: algorithmic and structural results ⋮ The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Amalgams and χ-Boundedness ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋮ Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors ⋮ Chi-boundedness of graph classes excluding wheel vertex-minors ⋮ On low rank-width colorings ⋮ Classes of graphs with no long cycle as a vertex-minor are polynomially \(\chi\)-bounded ⋮ VC-dimension and Erdős-Pósa property ⋮ Circle graphs are quadratically χ‐bounded ⋮ The grid theorem for vertex-minors ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure

Cites Work

• Unnamed Item
• The strong perfect graph theorem
• Covering and coloring polygon-circle graphs
• Graph minors. XVI: Excluding a non-planar graph
• Graph Theory and Probability
• Radius two trees specify χ‐bounded classes