Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00307
On Alliance Partitions and Bisection Width for Planar Graphs
Vol. 17, no. 6, pp. 599614, 2013. Regular paper.
Abstract An alliance in a graph is a set of vertices (allies) such that each vertex in the alliance has at least as many allies (counting the vertex itself) as nonallies in its neighborhood of the graph. We show how to construct infinitely many nontrivial examples of graphs that can not be partitioned into alliances and we show that any planar graph with minimum degree at least 4 can be split into two alliances in polynomial time. We base this on a proof of an upper bound of n on the bisection width for 4connected planar graphs with an odd number of vertices. This improves a recently published n+1 upper bound on the bisection width of planar graphs without separating triangles and supports the folklore conjecture that a general upper bound of n exists for the bisection width of planar graphs.

Submitted: May 2013.
Reviewed: September 2013.
Revised: October 2013.
Accepted: October 2013.
Final: October 2013.
Published: November 2013.
Communicated by
Subir Kumar Ghosh
