2023/12/13 by Édouard Bonnet, Bonnet, Édouard, Jędrzej Hodor +5 · 3 citations
Computer Science · Mathematics · #05C83 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2312.07962
openalex publication_date 2023/12/13 · openalex created_date 2023/12/15 · openalex updated_date 2026/07/28
A graph G contains a graph H as an induced minor if H can be obtained from G after vertex deletions and edge contractions. We show that for every k-vertex planar graph H, every graph G excluding H as an induced minor and Kt,t as a subgraph has treewidth at most Δ(G)f(k,t) where Δ(G) denotes the maximum degree of G. Without requiring the absence of a Kt,t subgraph, Korhonen [JCTB '23] has shown the upper bound of kO(1) 2Δ(G)5 whose dependence in Δ(G) is exponential. Our result partially answers a question of Chudnovsky [Dagstuhl seminar '23] asking whether the treewidth of graphs with Δ(G)=O(log|V(G)|) excluding both a k-vertex planar graph as an induced minor and the biclique Kt,t as a subgraph is in Ok,t(log |V(G)|). We confirm that the treewidth is in this case polylogarithmic in |V(G)|.