Low shrubdepth coloring conjecture for powers of nowhere dense classes

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 ⁣:NNf\colon \mathbb{N}\to\mathbb{N} such that, for every natural number pp and every nn-vertex graph GCdG\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.

Sources & referencesView supporting material

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.