2025/12/21 by Maria Chudnovsky, Julien Codsi, Chudnovsky, Maria +5
Computer Science · Mathematics · #05C40 #05C75 #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.2512.18835
openalex publication_date 2025/12/21 · openalex created_date 2025/12/24 · openalex updated_date 2026/07/28
Given a family H of graphs, we say that a graph G is H-induced-minor-free if no induced minor of G is isomorphic to a member of H, We denote by Wt× t the t-by-t hexagonal grid, and by Kt,t the complete bipartite graph with both sides of the bipartition of size t. We show that the class of \Kt,t,Wt× t\-induced minor-free graphs with bounded clique number has subpolynomial treewidth. Specifically, we prove that for every integer t there exist ε∈ (0,1] and c ∈ ℕ such that every n-vertex \Kt,t,Wt× t\-induced minor-free graph with no clique of size t has treewidth at most 2^clog1-εn.