TY - JOUR
T1 - Unfriendly partitions of a graph
AU - Aharoni, R.
AU - Milner, E. C.
AU - Prikry, K.
N1 - Funding Information:
when the first and by NSERC Grant
PY - 1990/10
Y1 - 1990/10
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0242368975&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0242368975&partnerID=8YFLogxK
U2 - 10.1016/0095-8956(90)90092-E
DO - 10.1016/0095-8956(90)90092-E
M3 - Article
AN - SCOPUS:0242368975
SN - 0095-8956
VL - 50
SP - 1
EP - 10
JO - Journal of Combinatorial Theory, Series B
JF - Journal of Combinatorial Theory, Series B
IS - 1
ER -