The list 2-coloring conjecture for countable acyclic digraphs

About 6 years old · traced to

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.

References

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.