Classes of graphs with small rank decompositions are -bounded

DOI10.1016/J.EJC.2011.12.005MaRDI QIDQ412260zbMATH OpenOpenAlexWikidataFDO

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Covering and coloring polygon-circle graphs
• Graph Theory and Probability
• Graph minors. XVI: Excluding a non-planar graph
• Radius two trees specify χ‐bounded classes
• The strong perfect graph theorem

Cited in

(17)

• Graphs of bounded cliquewidth are polynomially \(\chi\)-bounded
• 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
• Amalgams and \(\chi\)-boundedness
• Twin-width. III: Max independent set, min dominating set, and coloring
• 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

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)