Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity

2024/07/23 by Davies, James, Yuditsky, Yelena · 1 citation
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2407.16882

Abstract

We prove that for every positive integer d and forest F, the class of intersection graphs of axis-aligned boxes in ℝ^d with no induced F subgraph is (polynomially) χ-bounded.

Cited by

• Ramsey-type χ-bounds for χ-bounded graph classes

Related

• A note on the Gyárfás-Sumner conjecture
• Graphs of bounded chordality
• Boxicity and Maximum degree
• Induced subgraphs of graphs with large chromatic number. VII. Gyárfás' complementation conjecture
• Trees and near-linear stable sets