Classes of graphs with small rank decompositions are -bounded

DOI10.1016/J.EJC.2011.12.005zbMATH Open1237.05072arXiv1107.2161OpenAlexW2003779279WikidataQ57601373 ScholiaQ57601373MaRDI QIDQ412260FDOQ412260

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

Publication date: 4 May 2012

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

Abstract: 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.

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

Recommendations

• Graphs of bounded cliquewidth are polynomially \(\chi\)-bounded
• Amalgams and \(\chi\)-boundedness
• Radius two trees specify χ‐bounded classes
• Grad and classes with bounded expansion. I: Decompositions

zbMATH Keywords

chromatic numberclique numberbounded rank-widthchi-boundedclique width

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Graph Theory and Probability
• The strong perfect graph theorem
• Radius two trees specify χ‐bounded classes
• Graph minors. XVI: Excluding a non-planar graph
• Covering and coloring polygon-circle graphs

Cited In (17)

• The grid theorem for vertex-minors
• On low rank-width colorings
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• VC-dimension and Erdős-Pósa property
• Circle graphs are quadratically χ‐bounded
• The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor
• Classes of graphs with no long cycle as a vertex-minor are polynomially \(\chi\)-bounded
• Fair allocation algorithms for indivisible items under structured conflict constraints
• Twin-width. III: Max independent set, min dominating set, and coloring
• Amalgams and \(\chi\)-boundedness
• Rank-width: algorithmic and structural results
• Treewidth versus clique number. I: Graph classes with a forbidden structure
• Vertex-minors of graphs: a survey
• Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
• On low rank-width colorings
• Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
• Graphs of bounded cliquewidth are polynomially \(\chi\)-bounded

This page was built for publication: Classes of graphs with small rank decompositions are \(\chi \)-bounded

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412260)