Excluding subdivisions of bounded degree graphs Academic Article uri icon

abstract

  • 2018 Elsevier Inc. 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 . Dvok found a clever strengtheninghis 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 Dvok'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.

published proceedings

  • Journal of Combinatorial Theory Series B

altmetric score

  • 0.5

author list (cited authors)

  • Liu, C., & Thomas, R.

citation count

  • 3

complete list of authors

  • Liu, Chun-Hung||Thomas, Robin

publication date

  • January 2019