Unfriendly partitions of a graph

R. Aharoni, E. C. Milner, K. Prikry

Research output: Contribution to journalArticlepeer-review

30 Scopus citations

Abstract

It has been conjectured by Cowan and Emerson [3] that every graph has an unfriendly partition; i.e., there is a partition of the vertex set V = V0 {smile} V1 such that every vertex of Vi is joined to at least as many vertices in V1-i as to vertices in Vi. It is easily seen that every finite graph has such a partition, and hence by compactness so does any locally finite graph. We show that the conjecture is also true for graphs which satisfy one of the following two conditions: (i) there are only finitely many vertices having infinite degrees; (ii) there are a finite number of infinite cardinals m0 < m1 < ... < mk such that mi is regular for 1 ≤ i ≤ k, there are fewer than m0 vertices having finite degrees, and every vertex having infinite degree has degree mi for some i ≤ k.

Original languageEnglish (US)
Pages (from-to)1-10
Number of pages10
JournalJournal of Combinatorial Theory, Series B
Volume50
Issue number1
DOIs
StatePublished - Oct 1990

Bibliographical note

Funding Information:
when the first and by NSERC Grant

Fingerprint Dive into the research topics of 'Unfriendly partitions of a graph'. Together they form a unique fingerprint.

Cite this