Kreutzer et al.'s majority 3-colouring conjecture for digraphs

About 10 years old · traced to

Let DD be a digraph. A majority colouring of DD is a vertex colouring cc such that at least half of the out-neighbours of every vertex vv have a colour different from c(v)c(v). Kreutzer et al.'s conjecture. Every digraph has a majority 33-colouring. Kreutzer et al. proved that every digraph has a majority 44-colouring, and established the conjecture for digraphs satisfying certain sufficiently large out-degree or bounded in-degree conditions; the general case remains open.

References

Primary source

J. Bang-Jensen, F. Havet, M. Kriesell and A. Yeo, “Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties”, arXiv:2008.05272 (2020).

Additional references

4 papers in this index state this conjecture (2016–2020). The statement above is taken from the most recent of them; the others are arXiv:2003.10408, arXiv:1608.03040, arXiv:1608.06912.

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.