Unfriendly Partition Conjecture for countably infinite graphs

A majority 22-vertex-coloring of a graph is a coloring of its vertices with two colors such that, at every vertex, the number of neighbors having the same color is at most the number having the other color. Unfriendly Partition Conjecture. Every countably infinite graph admits a majority 22-vertex-coloring. This is the countably infinite restriction of the broader Cowan–Emerson conjecture. Every infinite graph admits a majority 33-vertex-coloring, but whether every countably infinite graph admits a majority 22-vertex-coloring remains open.

Sources & referencesView supporting material

Primary source

Rafał Kalinowski, Monika Pilśniak and Marcin Stawiski, “List majority edge-colorings of graphs”, arXiv:2312.00922 (2023).

Additional references

2 papers in this index state this conjecture (2020–2023). The statement above is taken from the most recent of them; the others are arXiv:2003.02883.

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.