## 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 = V_{0} {smile} V_{1} such that every vertex of V_{i} is joined to at least as many vertices in V_{1-i} as to vertices in V_{i}. 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 m_{0} < m_{1} < ... < m_{k} such that m_{i} is regular for 1 ≤ i ≤ k, there are fewer than m_{0} vertices having finite degrees, and every vertex having infinite degree has degree m_{i} for some i ≤ k.

Original language | English (US) |
---|---|

Pages (from-to) | 1-10 |

Number of pages | 10 |

Journal | Journal of Combinatorial Theory, Series B |

Volume | 50 |

Issue number | 1 |

DOIs | |

State | Published - Oct 1990 |

### Bibliographical note

Funding Information:when the first and by NSERC Grant