2010/10/01 by Ken‐ichi Kawarabayashi, Bruce Reed · 68 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Conjecture #Discrete mathematics #Graph #Limits and Structures in Graph Theory #Mathematics #Vertex (graph theory)
paper · doi:10.1109/focs.2010.22
openalex publication_date 2010/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
It is shown that for each t, there is a separator of size O(t√n) in any n-vertex graph G with no Kt-minor. This settles a conjecture of Alon, Seymour and Thomas (J. Amer. Math. Soc, 1990 and STOC'90), and generalizes a result of Djidjev (1981), and Gilbert, Hutchinson and Tarjan (J. Algorithm, 1984), independently, who proved that every graph with n vertices and genus g has a separator of order O(√gn), because Kthas genus Ω(t2). The bound O(t√n) is best possible because every 3-regular expander graph with n vertices is a graph with no Kt-minor for t = cn1/2, and with no separator of size dn for appropriately chosen positive constants c, d. In addition, we give an O(n2) time algorithm to obtain such a separator, and then give a sketch how to obtain such a separator in O(n1+ε) time for any ε > 0. Finally, we discuss several algorithm aspects of our separator theorem, including a possibility to obtain a separator of order g(t)√n, for some function g of t, in an n-vertex graph G with no Kt-minor in O(n) time.