Reed's constrained colouring conjecture

Let GG be a graph, and let LL be a (k+1)(k+1)-list assignment of GG, meaning that each vertex vv has a list L(v)L(v) of k+1k+1 available colours. Suppose that for every vertex vv of GG and every colour cL(v)c\in L(v), at most kk neighbours wNG(v)w\in N_G(v) satisfy cL(w)c\in L(w). Reed's constrained colouring conjecture. There exists a proper LL-colouring of GG. This conjecture strengthens ordinary list-colourability conditions by controlling the number of neighbours sharing each available colour; its status is not resolved in the supplied source.

Sources & referencesView supporting material

Primary source

Ian M. Wanless and David R. Wood, “A general framework for hypergraph colouring”, arXiv:2008.00775 (2021).

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.