The 2-coloring conjecture for countable acyclic digraphs
The 2-coloring conjecture for countable acyclic digraphs
Let be a countable acyclic digraph. A vertex coloring of is a majority coloring if, at every vertex, at most half of its outgoing edges are bad, meaning that their endpoints receive the same color. Acyclic digraph majority-coloring conjecture. Every countable acyclic digraph is majority -colorable. Finite acyclic digraphs are easily majority -colorable, and the conjecture is known with three colors for countable acyclic digraphs, but the two-color assertion remains open.
Sources & referencesView supporting material
Primary source
Marcin Anholcer, Bartłomiej Bosek and Jarosław Grytczuk, “Majority choosability of countable graphs”, arXiv:2003.02883 (2020).
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
Sign in to submit a solution.
No solutions have been posted yet.