{
  "id": "2311.03341",
  "version": "v1",
  "published": "2023-11-06T18:47:44.000Z",
  "updated": "2023-11-06T18:47:44.000Z",
  "title": "On polynomial degree-boundedness",
  "authors": [
    "Romain Bourneuf",
    "Matija Bucić",
    "Linda Cook",
    "James Davies"
  ],
  "comment": "10 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We prove a conjecture of Bonamy, Bousquet, Pilipczuk, Rz\\k{a}\\.zewski, Thomass\\'e, and Walczak, that for every graph $H$, there is a polynomial $p$ such that for every positive integer $s$, every graph of average degree at least $p(s)$ contains either $K_{s,s}$ as a subgraph or contains an induced subdivision of $H$. This improves upon a result of K\\\"uhn and Osthus from 2004 who proved it for graphs whose average degree is at least triply exponential in $s$ and a recent result of Du, Gir\\~{a}o, Hunter, McCarty and Scott for graphs with average degree at least singly exponential in $s$. As an application, we prove that the class of graphs that do not contain an induced subdivision of $K_{s,t}$ is polynomially $\\chi$-bounded. In the case of $K_{2,3}$, this is the class of theta-free graphs, and answers a question of Davies. Along the way, we also answer a recent question of McCarty, by showing that if ${\\cal G}$ is a hereditary class of graphs for which there is a polynomial $p$ such that every bipartite $K_{s,s}$-free graph in $\\mathcal{G}$ has average degree at most $p(s)$, then more generally, there is a polynomial $p'$ such that every $K_{s,s}$-free graph in $\\mathcal{G}$ has average degree at most $p'(s)$. Our main new tool is an induced variant of the K\\H{o}v\\'ari-S\\'os-Tur\\'an theorem, which we find to be of independent interest.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-11-06T18:47:44.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "average degree",
      "polynomial degree-boundedness",
      "induced subdivision",
      "exponential",
      "theta-free graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}