Dominated balanced separators in wheel-induced-minor-free graphs
By: Maria Chudnovsky , J. Pascal Gollin , Matjaž Krnc and more
Gartland and Lokshtanov conjectured that every graph that excludes some planar graph as an induced minor has a balanced separator, that is, a separator whose deletion leaves every component with no more than half of the vertices of the graph, which is dominated by a bounded number of vertices. We confirm this conjecture for excluding any fixed wheel, that is, a cycle together with a universal vertex, as an induced minor.
Similar Papers
Separator Theorem for Minor-Free Graphs in Linear Time
Data Structures and Algorithms
Finds a good split for tricky computer networks fast.
Excluding an induced wheel minor in graphs without large induced stars
Combinatorics
Solves hard computer problems on special graphs.
Rankwidth of Graphs with Balanced Separations: Expansion for Dense Graphs
Combinatorics
Finds hidden patterns in connected things.