Characterization of clustered coloring number in minor-closed classes
Characterization of clustered coloring number in minor-closed classes
Let be an integer. For a graph class , let be the least integer for which there is a constant such that every graph has . The graphs are complete bipartite graphs, and is the graph formed from a path on vertices by adding vertices adjacent to every path vertex. Conjecture on clustered coloring number. A minor-closed class of graphs satisfies
if and only if there exists such that
The preceding observation shows that the condition is necessary: bounded clustered coloring number excludes all but finitely many graphs of these two forms. The conjecture asserts sufficiency for minor-closed classes, giving an exact characterization; the paper presents it as an open question.
Sources & referencesView supporting material
Primary source
Zdeněk Dvořák and Sergey Norin, “Islands in minor-closed classes. I. Bounded treewidth and separators”, arXiv:1710.02727 (2017).
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.