The unfriendly partition conjecture for countable graphs

Let GG be a countable graph. An unfriendly bipartition of GG is a bipartition of V(G)V(G) such that every vertex has at least as many neighbours in the other class as in its own.

Unfriendly partition conjecture. Every countable graph admits an unfriendly bipartition.

Every finite graph has an unfriendly bipartition, but the corresponding assertion for countably infinite graphs is a major open problem in infinite graph theory.

Sources & referencesView supporting material

Primary source

Jan Ouborny and Max Pitz, “All graphs are majority 3-choosable”, arXiv:2505.06031 (2025).

Additional references

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

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.