Back to Search Start Over

Polynomial Gy\'arf\'as-Sumner conjecture for graphs of bounded boxicity

Authors :
Davies, James
Yuditsky, Yelena
Publication Year :
2024

Abstract

We prove that for every positive integer $d$ and forest $F$, the class of intersection graphs of axis-aligned boxes in $\mathbb{R}^d$ with no induced $F$ subgraph is (polynomially) $\chi$-bounded.<br />Comment: 10 pages

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2407.16882
Document Type :
Working Paper