## 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}. Dvořák 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 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 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.

Original language | English (US) |
---|---|

Pages (from-to) | 1-35 |

Number of pages | 35 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 134 |

DOIs | |

State | Published - Jan 2019 |

Externally published | Yes |

## 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