Excluding subdivisions of bounded degree graphs

Chun Hung Liu, Robin Thomas

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 H1. Dvořák found a clever strengthening—his structure is not satisfied by graphs that contain a subdivision of a graph H2, where H2 has “similar embedding properties” as H. Building upon Dvořák'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 H3 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.

Original languageEnglish (US)
Pages (from-to)1-35
Number of pages35
JournalJournal of Combinatorial Theory. Series B
Volume134
DOIs
StatePublished - Jan 2019

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Excluded subdivision theorem
  • Graph subdivision
  • Structure theorem

Fingerprint Dive into the research topics of 'Excluding subdivisions of bounded degree graphs'. Together they form a unique fingerprint.

Cite this