Characterization of clustered coloring number in minor-closed classes

Let t1t\geq 1 be an integer. For a graph class G\mathcal{G}, let col(G)\operatorname{col}_\star(\mathcal{G}) be the least integer tt for which there is a constant C1C\geq 1 such that every graph GGG\in\mathcal{G} has colC(G)t\operatorname{col}_C(G)\leq t. The graphs Kt,mK_{t,m} are complete bipartite graphs, and It1+PmI_{t-1}+P_m is the graph formed from a path on mm vertices by adding t1t-1 vertices adjacent to every path vertex. Conjecture on clustered coloring number. A minor-closed class of graphs G\mathcal{G} satisfies

col(G)t\operatorname{col}_\star(\mathcal{G})\leq t

if and only if there exists m1m\geq 1 such that

Kt,mGandIt1+PmG.K_{t,m}\notin\mathcal{G}\quad\text{and}\quad I_{t-1}+P_m\notin\mathcal{G}.

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

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.