Cluster-critical class characterization of clustered chromatic number

Let M\mathcal{M} be a minor-closed class of graphs, and let k0k\geqslant 0 be an integer. A graph class is kk-cluster critical if it is obtained as a wedge-product of vv copies of I\mathcal{I} and pp copies of P\mathcal{P}, in some order, with v+2p=k+1v+2p=k+1. Cluster-critical conjecture.

χ(M)k+1\chi_{\star}(\mathcal{M})\geqslant k+1

if and only if G⊈M\mathcal{G}\not\subseteq\mathcal{M} for some kk-cluster critical class G\mathcal{G}. This reformulates the preceding obstruction conjecture in terms of wedge-products and cluster-critical classes. The source presents it as a conjectural characterization; no general proof or refutation is given.

Sources & referencesView supporting material

Primary source

Sergey Norin, Alex Scott, Paul Seymour and David R. Wood, “Clustered Colouring in Minor-Closed Classes”, arXiv:1708.02370 (2018).

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.