Unfriendly partitions
Status partial high confidence
The problem of whether every countably infinite graph has an unfriendly partition into two sets remains open. Significant partial results have appeared since 2007: the conjecture has been confirmed for rayless graphs, for graphs not containing a subdivision of an infinite clique, for line graphs of any cardinality, and most recently (2024) for all countable graphs without alternating rays — rays that pass through infinitely many vertices of both finite and infinite degree. The difficult case of countable graphs that do admit alternating rays is still unresolved.
Cited literature (4)
-
Proves an equivalence: the existence of unfriendly partitions for all countable graphs is equivalent to their existence for all countable graphs lacking induced subgraphs of infinite minimum degree, and establishes omega_n-unfriendly partitions for graphs with infinite minimum degree.
-
Proves the Unfriendly Partition Conjecture for line graphs of any cardinality by showing they admit majority vertex-colorings from lists of size 2.
-
Shows that the minimum cardinality of a graph (without vertices of finite degree) that admits no unfriendly partition cannot be determined in ZFC, establishing a set-theoretic independence result.
-
Proves that every countable graph without alternating rays admits an unfriendly partition, strictly generalizing results of Aharoni-Milner-Prikry and Bruhn-Diestel-Georgakopoulos-Sprüssel.
Reviewer notes. The Bruhn-Diestel-Georgakopoulos-Sprüssel (2010) paper on rayless graphs and the Berger (2017) paper on graphs without a subdivision of an infinite clique are both cited in verified sources as important post-2007 partial results, but their direct URLs could not be individually fetched and confirmed in this review, so they are not listed in since_posted. The published journal version of the line graphs paper (Combinatorica 45, 2025, DOI 10.1007/s00493-024-00131-1) was inaccessible via Springer; the arXiv preprint (2312.00922) was verified instead. The December 2024 paper (2412.14151) explicitly states the problem remains open for countable graphs that do admit alternating rays.
Discussion
It is a simple property that every finite graph $ G $ has an unfriendly partition into two sets - just choose a partition of $ V(G) $ into two sets so that the number of edges with one end in each is maximum. Cowan and Emerson [CE] conjectured that the same property should hold true of infinite graphs. A counterexample to this was constructed by Milner and Shelah [MS], but their construction uses uncountably many vertices, leaving the countable case (highlighted above) still open. In the same article by Milner and Shelah [MS], they show that every graph does have an unfriendly partition into three sets. Curiously, it is quite easy to see that the answer to the above question is yes in the case when all vertices have finite degree, and also in the case when all vertices have infinite degree. The former follows from the unfriendly partition property for finite graphs together with a standard compactness argument. The latter can be achieved with a "back and forth" construction. Thus, the difficult case is the mixed one. Aharoni, Milner, and Prikry [AMP] showed that every graph with only finitely many vertices of infinite degree has an unfriendly partition into two sets, but this seems the extent of our knowledge. It does not appear that there is any consensus among experts as to whether this conjecture should be true or false.
Bibliography
-
★
[CE]R. Cowan and W. Emerson, Proportional colorings of graphs, unpublished. -
[MS]E. C. Milner and S. Shelah, Graphs with no unfriendly partitions. A tribute to Paul Erdös, 373--384, Cambridge Univ. Press, Cambridge, 1990. MathSciNet . MathSciNet -
[AMP]R. Aharoni, E. C. Milner, K. Prikry, Unfriendly partitions of a graph. J. Combin. Theory Ser. B 50 (1990), no. 1, 1--10. MathSciNet MathSciNet