Low shrubdepth coloring conjecture for powers of nowhere dense classes
Let be a nowhere dense class of graphs, let be a positive integer, and let be a positive real. For a graph , write for its th power, and let shrubdepth denote the structural parameter used for dense graph classes. Low shrubdepth coloring conjecture. There is a function such that, for every natural number and every -vertex graph , has a coloring with colors in which every subgraph induced by a subset of colors has shrubdepth at most . 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
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.