The list Unfriendly Partition Conjecture for countable graphs

Let GG be a countable graph, and assign to each vertex vv a list L(v)L(v) of available colors. The graph 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 each vertex the number of incident monochromatic edges is at most the number of incident edges whose endpoints have different colors. List Unfriendly Partition Conjecture. Every countable graph is majority 22-choosable. This strengthens the Unfriendly Partition Conjecture. The paper proves the weaker bound that every countable graph is majority 44-choosable, so the conjectured bound 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.