2026-09-08T01:21:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26489 2026-09-05T19:45:15Z ddc:004 open_access

The Price of Homogeneity Is Polynomial Gorsky, Maximilian Seweryn, Michał T. Wiederrecht, Sebastian Graph Minors Grid Graph Wall Graph Homogeneous Wall Colored Graph Annotated Graph Structural Graph Theory Irrelevant Vertex Technique We provide explicit and polynomial bounds for the Homogeneous Wall Lemma which occurred for the first time implicitly in the 13th entry of Robertson and Seymour’s Graph Minors Series [JCTB 1990] and has since become a cornerstone in the algorithmic theory of graph minors. A wall where each brick is assigned a set of colours is said to be homogeneous if each brick is assigned the same set of colours. The Homogeneous Wall Lemma says that there exists a function h that, given non-negative integers q and k and an h(q,k)-wall W where each brick is assigned a, possibly empty, subset of {1,…,q} contains a k-wall W' as a subgraph such that, if one assigns to each brick B of W' the union of the sets assigned to the bricks of W in its interior, then W' is homogeneous. It is well-known that h(q,k) ∈ k^𝒪(q). The Homogeneous Wall Lemma plays a key role in most applications of the Irrelevant Vertex Technique where an exponential dependency of h on q usually causes non-uniform dependencies on meta-parameters at best and additional exponential blow-ups at worst. By proving that h(q,k) ∈ 𝒪(q⁴⋅ k⁶), we provide a positive answer to a problem raised by Sau, Stamoulis, and Thilikos [ICALP 2020]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Maximilian Gorsky and Michał T. Seweryn and Sebastian Wiederrecht 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.100 urn:nbn:de:0030-drops-264891 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.100 eng https://creativecommons.org/licenses/by/4.0/legalcode