Geodesic
On Alliance Partitions and Bisection Width for Planar Graphs
Journal of graph algorithms and applications, Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Computation, WALCOM 2013 , Tome 17 (2013) no. 6, pp. 599-614 Cet article a éte moissonné depuis la source Journal of Graph Algorythms and Applications website

Voir la notice de l'article

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.
DOI : 10.7155/jgaa.00307
Keywords: Alliances, Planar Graphs, Bisection Width 
@article{JGAA_2013_17_6_a1,
     author = {Martin Olsen and Morten Revsbaek},
     title = {On {Alliance} {Partitions} and {Bisection} {Width} for {Planar} {Graphs}},
     journal = {Journal of graph algorithms and applications},
     pages = {599--614},
     year = {2013},
     volume = {17},
     number = {6},
     doi = {10.7155/jgaa.00307},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00307/}
}
TY  - JOUR
AU  - Martin Olsen
AU  - Morten Revsbaek
TI  - On Alliance Partitions and Bisection Width for Planar Graphs
JO  - Journal of graph algorithms and applications
PY  - 2013
SP  - 599
EP  - 614
VL  - 17
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00307/
DO  - 10.7155/jgaa.00307
LA  - en
ID  - JGAA_2013_17_6_a1
ER  - 
%0 Journal Article
%A Martin Olsen
%A Morten Revsbaek
%T On Alliance Partitions and Bisection Width for Planar Graphs
%J Journal of graph algorithms and applications
%D 2013
%P 599-614
%V 17
%N 6
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00307/
%R 10.7155/jgaa.00307
%G en
%F JGAA_2013_17_6_a1
Martin Olsen; Morten Revsbaek. On Alliance Partitions and Bisection Width for Planar Graphs. Journal of graph algorithms and applications, 
							Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Computation, WALCOM 2013
					, Tome 17 (2013) no. 6, pp. 599-614. doi: 10.7155/jgaa.00307

Cité par Sources :