The list 2-coloring conjecture for countable acyclic digraphs
The list 2-coloring conjecture for countable acyclic digraphs
Let be a countable acyclic digraph, and assign to each vertex a list of available colors. The digraph is majority -choosable if, for every such assignment with , it has a majority coloring using a color from at each vertex, where at every vertex at most half of its outgoing edges are bad. Acyclic digraph list-coloring conjecture. Every countable acyclic digraph is majority -choosable. The greedy algorithm proves the analogous statement for finite acyclic digraphs, but the countable list version is left 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.