Graphs of bounded cliquewidth are polynomially χ-bounded

2019/10/01 by Bonamy, Marthe, Pilipczuk, Michał
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1910.00697

Abstract

We prove that if C is a hereditary class of graphs that is polynomially χ-bounded, then the class of graphs that admit decompositions into pieces belonging to C along cuts of bounded rank is also polynomially χ-bounded. In particular, this implies that for every positive integer k, the class of graphs of cliquewidth at most k is polynomially χ-bounded.

Related

• Reuniting χ-boundedness with polynomial χ-boundedness
• Classes of graphs with small rank decompositions are chi-bounded
• Families of Linearly χ-bounded Graphs without Chair or its Induced Sub-graphs
• Graphs of bounded twin-width are quasi-polynomially χ-bounded
• Polynomial bounds for pathwidth