Excluding subdivisions of bounded degree graphs

DOI10.1016/J.JCTB.2018.05.001MaRDI QIDQ1633742zbMATH OpenOpenAlexFDO

Authors Chun-Hung Liu, Robin Thomas

Publication date 20 December 2018

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.4428

zbMATH Keywords

excluded subdivision theoremgraph subdivisionstructure theorem

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: Let $H$ be a fixed graph. What can be said about graphs $G$ that have no subgraph isomorphic to a subdivision of $H$? Grohe and Marx proved that such graphs $G$ satisfy a certain structure theorem that is not satisfied by graphs that contain a subdivision of a (larger) graph $H_1$. Dvov{r}'ak found a clever strengthening---his structure is not satisfied by graphs that contain a subdivision of a graph $H_2$, where $H_2$ has "similar embedding properties" as $H$. Building upon Dvov{r}'ak's theorem, we prove that said graphs $G$ satisfy a similar structure theorem. Our structure is not satisfied by graphs that contain a subdivision of a graph $H_3$ that has similar embedding properties as $H$ and has the same maximum degree as $H$. This will be important in a forthcoming application to well-quasi-ordering.

Recommendations

• Induced subdivisions and bounded expansion
• A short derivation of the structure theorem for graphs with excluded topological minors
• Excluding a substar and an antisubstar
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• Topological minors in graphs of large girth

Cites work

• Excluding a countable clique
• Graph minors. IX: Disjoint crossed paths
• Graph minors. X: Obstructions to tree-decomposition
• Graph minors. XI: Circuits on a surface
• Graph minors. XII: Distance on a surface
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XIV: Extending an embedding
• Graph minors. XVI: Excluding a non-planar graph
• Immersions in highly edge connected graphs
• Important separators and parameterized algorithms
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs

Cited in

(7)

• Excluding a countable clique
• Clustered variants of Hajós' conjecture
• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three
• Recent progress on well-quasi-ordering graphs
• Excluding Subdivisions of Infinite Cliques
• Excluding a substar and an antisubstar
• Packing topological minors half‐integrally

This page was built for publication: Excluding subdivisions of bounded degree graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1633742)