The Pollyanna conjecture for box intersection graphs

From papers

Fix a positive integer dd, and let Bd\mathcal{B}_d be the class of intersection graphs of axis-aligned boxes in Rd\mathbb{R}^d. A hereditary class is Pollyanna if every hereditary χ-bounded subclass of it is polynomially χ-bounded. Pollyanna conjecture for box intersection graphs. The class Bd\mathcal{B}_d is Pollyanna. This would generalize the known polynomial χ-boundedness results for interval graphs and rectangle intersection graphs; the source presents it as a possible broader principle and does not state a resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

James Davies and Yelena Yuditsky, “Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity”, arXiv:2407.16882 (2024).

Additional references

2 papers in this index state this conjecture (2023–2024). The statement above is taken from the most recent of them; the others are arXiv:2310.11167.

Solutions 0

No solutions have been posted yet.