Shelah, Saharon; Milner, E. C. Graphs with no unfriendly partitions. (English) Zbl 0723.05058 A tribute to Paul Erdős, 373-384 (1990). [For the entire collection see Zbl 0706.00007.] Authors’ abstract: “An unfriendly n-partition of a graph \(G=(V,E)\) is a map c: \(V\to \{0,1,...,n-1\}\) such that, for every vertex x, there holds \[ | \{y\in E(x): c(x)=c(y)\}| \leq | \{y\in E(x): c(x)\neq c(y)\}|, \] where E(x) is the set of vertices joined to x by an edge of G. We disprove a conjecture of Cowen and Emerson by showing that there is a graph which has no unfriendly 2-partition. However, we also show that every graph has an unfriendly 3-partition.” Reviewer: M.Kubale (Gdańsk) Cited in 13 Documents MSC: 05C15 Coloring of graphs and hypergraphs Keywords:vertex degree; vertex partitions; unfriendly n-partition Citations:Zbl 0706.00007 PDFBibTeX XMLCite \textit{S. Shelah} and \textit{E. C. Milner}, in: A tribute to Paul Erdős. Cambridge etc.: Cambridge University Press. 373--384 (1990; Zbl 0723.05058)