Low shrubdepth coloring conjecture for powers of nowhere dense classes
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.