The list 2-coloring conjecture for countable acyclic digraphs

Let DD be a countable acyclic digraph, and assign to each vertex vv a list L(v)L(v) of available colors. The digraph is majority kk-choosable if, for every such assignment with L(v)=k|L(v)|=k, it has a majority coloring using a color from L(v)L(v) 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 22-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

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.