1990/10/01 by Noga Alon, Paul Seymour, Robin Thomas · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Computational Geometry and Mesh Generation #Mathematics #Combinatorics #Vertex (graph theory) #Joins #Planar graph #Neighbourhood (mathematics) #Partition (number theory) #Discrete mathematics #Wheel graph #Graph #Graph power #Line graph
paper · pdf · doi:10.2307/1990903
openalex publication_date 1990/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
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 h3/2n1/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(h1/2n1/2m), where m = | V(G) | + | E(G) |.