×

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)

MSC:

05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 0706.00007
PDFBibTeX XMLCite