NSSW excluded-configuration conjecture for minor-closed classes

Let Xk,c\mathcal{X}_{k,c} be the graph family defined in the source, and let M\mathcal{M} be a minor-closed class. NSSW excluded-configuration conjecture. Every minor-closed class that excludes every graph in Xk,c\mathcal{X}_{k,c} for some integer cc is kk-colourable with bounded clustering.

Equivalently, for every minor-closed class M\mathcal{M}, χ(M)\chi_{\star}(\mathcal{M}) should equal the minimum integer kk such that MXk,c=\mathcal{M}\cap\mathcal{X}_{k,c}=\varnothing for some integer cc. The source provides the construction and a rainbow-clique obstruction, but does not establish the conjecture in general.

Sources & referencesView supporting material

Primary source

David R. Wood, “Defective and Clustered Graph Colouring”, arXiv:1803.07694 (2018).

Additional references

2 papers in this index state this conjecture (2017–2018). The statement above is taken from the most recent of them; the others are arXiv:1708.02370.

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.