Low shrubdepth coloring conjecture for powers of nowhere dense classes

About 6 years old · traced to

Let C\mathcal{C} be a nowhere dense class of graphs, let dd be a positive integer, and let ε\varepsilon be a positive real. For a graph GG, write GdG^d for its ddth power, and let shrubdepth denote the structural parameter used for dense graph classes. Low shrubdepth coloring conjecture. There is a function f ⁣:N→Nf\colon \mathbb{N}\to\mathbb{N} such that, for every natural number pp and every nn-vertex graph G∈CdG\in\mathcal{C}^d, GG has a coloring with O(nε)\mathcal{O}(n^{\varepsilon}) colors in which every subgraph induced by a subset of pp colors has shrubdepth at most f(p)f(p). This conjecture seeks to extend the corresponding low shrubdepth coloring theorem from bounded expansion classes to powers of nowhere dense classes; the cited arguments for bounded expansion do not generalize to the nowhere dense setting, and the conjecture remains open.

References

Primary source

Marcin Briański, Piotr Micek, Michał Pilipczuk and Michał T. Seweryn, “Erdős-Hajnal properties for powers of sparse graphs”, arXiv:2006.01500 (2020).

Additional references

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.