The surface \ce 3-system list-colouring conjecture

About 18 years old · traced to

Let SS be a fixed surface. For a graph GG embeddable on SS with a Σ\Sigma-system, define

k(G;Σ)=max⁡u≠v∣Σ(u)∩Σ(v)∣k(G;\Sigma)=\max_{u\ne v}|\Sigma(u)\cap\Sigma(v)|

and let Δ(G;Σ)=max⁡v∣Σ(v)∣\Delta(G;\Sigma)=\max_{v}|\Sigma(v)|. The surface Σ\Sigma-system list-colouring conjecture. There exists a constant cSc_S such that, for every graph GG embeddable on SS,

ch(G;Σ)≤Δ(G;Σ)+k(G;Σ)+cS.\mathit{ch}(G;\Sigma)\le\Delta(G;\Sigma)+k(G;\Sigma)+c_S.

This aims to combine the paper's main theorem with a degeneracy-based list-colouring bound, extending the latter to surface-embeddable graphs. The source gives no resolution.

References

Primary source

Omid Amini, Louis Esperet and Jan van den Heuvel, “A Unified Approach to Distance-Two Colouring of Graphs on Surfaces”, arXiv:0812.1345 (2012).

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.