On Alliance Partitions and Bisection Width for Planar Graphs
Vol. 17, no. 6, pp. 599-614, 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 non-allies in its neighborhood of the graph. We show how to construct infinitely many non-trivial 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 4-connected 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
article (PDF)