The 2-coloring conjecture for countable acyclic digraphs

Let DD be a countable acyclic digraph. A vertex coloring of DD 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 22-colorable. Finite acyclic digraphs are easily majority 22-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

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.