Kreutzer et al.'s majority 3-colouring conjecture for digraphs
Let be a digraph. A majority colouring of is a vertex colouring such that at least half of the out-neighbours of every vertex have a colour different from . Kreutzer et al.'s conjecture. Every digraph has a majority -colouring. Kreutzer et al. proved that every digraph has a majority -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
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.