Geodesic
A separator theorem for nonplanar graphs
Journal of the American Mathematical Society, Tome 03 (1990) no. 4, pp. 801-808

Voir la notice de l'article provenant de la source American Mathematical Society

Let $G$ be an $n$-vertex graph with no minor isomorphic to an $h$-vertex complete graph. We prove that the vertices of $G$ can be partitioned into three sets $A,\;B,\;C$ such that no edge joins a vertex in $A$ with a vertex in $B$, neither $A$ nor $B$ contains more than $2n/3$ vertices, and $C$ contains no more than ${h^{3/2}}{n^{1/2}}$ vertices. This extends a theorem of Lipton and Tarjan for planar graphs. We exhibit an algorithm which finds such a partition $(A,\;B,\;C)$ in time $O({h^{1/2}}{n^{1/2}}m)$, where $m = \left | {V(G)} \right | + \left | {E(G)} \right |$. 
@article{10_1090_S0894_0347_1990_1065053_0,
     author = {Alon, Noga and Seymour, Paul and Thomas, Robin},
     title = {A separator theorem for nonplanar graphs},
     journal = {Journal of the American Mathematical Society},
     pages = {801--808},
     publisher = {mathdoc},
     volume = {03},
     number = {4},
     year = {1990},
     doi = {10.1090/S0894-0347-1990-1065053-0},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1990-1065053-0/}
}
TY  - JOUR
AU  - Alon, Noga
AU  - Seymour, Paul
AU  - Thomas, Robin
TI  - A separator theorem for nonplanar graphs
JO  - Journal of the American Mathematical Society
PY  - 1990
SP  - 801
EP  - 808
VL  - 03
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1990-1065053-0/
DO  - 10.1090/S0894-0347-1990-1065053-0
ID  - 10_1090_S0894_0347_1990_1065053_0
ER  - 
%0 Journal Article
%A Alon, Noga
%A Seymour, Paul
%A Thomas, Robin
%T A separator theorem for nonplanar graphs
%J Journal of the American Mathematical Society
%D 1990
%P 801-808
%V 03
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1990-1065053-0/
%R 10.1090/S0894-0347-1990-1065053-0
%F 10_1090_S0894_0347_1990_1065053_0
Alon, Noga; Seymour, Paul; Thomas, Robin. A separator theorem for nonplanar graphs. Journal of the American Mathematical Society, Tome 03 (1990) no. 4, pp. 801-808. doi: 10.1090/S0894-0347-1990-1065053-0

[1] Gilbert, John R., Hutchinson, Joan P., Tarjan, Robert Endre A separator theorem for graphs of bounded genus J. Algorithms 1984 391 407

[2] Lipton, Richard J., Tarjan, Robert Endre A separator theorem for planar graphs SIAM J. Appl. Math. 1979 177 189

[3] Seymour, P. D., Thomas, Robin Graph searching and a min-max theorem for tree-width J. Combin. Theory Ser. B 1993 22 33

Cité par Sources :