Unfriendly partition
 |
Unsolved problem in mathematics: Does every countable graph have an unfriendly partition into two parts? (more unsolved problems in mathematics)
|
In the mathematics of infinite graphs, an unfriendly partition or majority coloring is a partition of the vertices of the graph into disjoint subsets, so that every vertex has at least as many neighbors in other sets as it has in its own set. It is a generalization of the concept of a maximum cut for finite graphs, which is automatically an unfriendly partition. (If not, a vertex with more neighbors in its own set could be moved to the other set, increasing the number of cut edges.) The unfriendly partition conjecture is an unsolved problem asking whether every countable graph has an unfriendly partition into two subsets.[1]
Robert H. Cowan and William R. Emerson, in unpublished work, conjectured that every infinite graph has an unfriendly partition into two subsets. However, Saharon Shelah and Eric Charles Milner disproved the conjecture, showing that uncountable graphs might not have two-subset unfriendly partitions. Nevertheless, they showed that an unfriendly partition into three subsets always exists.[2]
Among countable graphs, the existence of a two-subset unfriendly partition is known for the following special cases:
- Graphs that have finitely many vertices of infinite degree[3]
- Graphs in which all vertices have infinite degree, by an argument using the back-and-forth method[1]
- Graphs with no end[4]
- Graphs without a subdivision of an infinite clique[5]
The case for arbitrary countable graphs remains open.[1]
References
- ↑ 1.0 1.1 1.2 DeVos, Matthew (October 22, 2007), "Unfriendly partitions", Open problem garden, http://www.openproblemgarden.org/op/unfriendly_partitions
- ↑ Baker, A.; Bollobás, B.; Hajnal, A., eds. (1990), "Graphs with no unfriendly partitions", A tribute to Paul Erdős, Cambridge University Press, pp. 373–384, doi:10.1177/016502549001300309, https://shelah.logic.at/files/129081/graphs-with-no-unfriendly-partitions.pdf
- ↑ Aharoni, R.; Milner, E. C.; Prikry, K. (1990), "Unfriendly partitions of a graph", Journal of Combinatorial Theory, Series B 50 (1): 1–10, doi:10.1016/0095-8956(90)90092-E
- ↑ Bruhn, Henning; Diestel, Reinhard; Georgakopoulos, Agelos; Sprüssel, Philipp (2010), "Every rayless graph has an unfriendly partition", Combinatorica 30 (5): 521–532, doi:10.1007/s00493-010-2590-3
- ↑ Berger, Eli (2017), "Unfriendly partitions for graphs not containing a subdivision of an infinite clique", Combinatorica 37 (2): 157–166, doi:10.1007/s00493-015-3261-1
 |  |
