In the mathematics of

infinite graph This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B ...

s, an unfriendly partition or majority coloring is a

partition Partition may refer to: Computing Hardware * Disk partitioning, the division of a hard disk drive * Memory partition, a subdivision of a computer's memory, usually for use by a single job Software * Partition (database), the division of a ...

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 a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets and , such that the number of edges between and is as large as possible. Fin ...

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 In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...

graph has an unfriendly partition into two subsets. 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 Saharon Shelah ( he, שהרן שלח; born July 3, 1945) is an Israeli mathematician. He is a professor of mathematics at the Hebrew University of Jerusalem and Rutgers University in New Jersey. Biography Shelah was born in Jerusalem on July 3, ...

and Eric Charles Milner disproved the conjecture, showing that

uncountable In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal num ...

graphs might not have two-subset unfriendly partitions. Nevertheless, they showed that an unfriendly partition into three subsets always exists. 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 *Graphs in which all vertices have infinite degree, by an argument using the

back-and-forth method In mathematical logic, especially set theory and model theory, the back-and-forth method is a method for showing isomorphism between countably infinite structures satisfying specified conditions. In particular it can be used to prove that * any t ...

*Graphs with no

end End, END, Ending, or variation, may refer to: End *In mathematics: ** End (category theory) ** End (topology) **End (graph theory) ** End (group theory) (a subcase of the previous) **End (endomorphism) *In sports and games **End (gridiron footbal ...

*Graphs without a

subdivision Subdivision may refer to: Arts and entertainment * Subdivision (metre), in music * ''Subdivision'' (film), 2009 * "Subdivision", an episode of ''Prison Break'' (season 2) * ''Subdivisions'' (EP), by Sinch, 2005 * "Subdivisions" (song), by Rus ...

of an infinite

clique A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...

The case for arbitrary countable graphs remains open.

References

{{reflist, refs= {{citation , last1 = Aharoni , first1 = R. , last2 = Milner , first2 = E. C. , last3 = Prikry , first3 = K. , doi = 10.1016/0095-8956(90)90092-E , issue = 1 , journal = Journal of Combinatorial Theory , mr = 1070461 , pages = 1–10 , series = Series B , title = Unfriendly partitions of a graph , volume = 50 , year = 1990, doi-access = free {{citation , last1 = Bruhn , first1 = Henning , last2 = Diestel , first2 = Reinhard , last3 = Georgakopoulos , first3 = Agelos , last4 = Sprüssel , first4 = Philipp , doi = 10.1007/s00493-010-2590-3 , issue = 5 , journal = Combinatorica , mr = 2776717 , pages = 521–532 , title = Every rayless graph has an unfriendly partition , volume = 30 , year = 2010, s2cid = 9304176 {{citation , last = Berger , first = Eli , doi = 10.1007/s00493-015-3261-1 , issue = 2 , journal = Combinatorica , mr = 3638340 , pages = 157–166 , title = Unfriendly partitions for graphs not containing a subdivision of an infinite clique , volume = 37 , year = 2017, s2cid = 254028041 {{citation, url=http://www.openproblemgarden.org/op/unfriendly_partitions, title=Unfriendly partitions, work=Open problem garden, first=Matthew, last=DeVos, date=October 22, 2007 {{citation , last1 = Shelah , first1 = Saharon , author1-link = Saharon Shelah , last2 = Milner , first2 = E. C. , author2-link = Eric Charles Milner , editor1-last = Baker , editor1-first = A. , editor2-last = Bollobás , editor2-first = B. , editor3-last = Hajnal , editor3-first = A. , contribution = Graphs with no unfriendly partitions , contribution-url = https://shelah.logic.at/files/129081/graphs-with-no-unfriendly-partitions.pdf , doi = 10.1177/016502549001300309 , mr = 1117030 , pages = 373–384 , publisher = Cambridge University Press , title = A tribute to Paul Erdős , year = 1990, s2cid = 143480036 Graph theory objects Infinite graphs Unsolved problems in graph theory