A positive instance of Scott's Conjecture on induced subdivisions
Abstract
For a graph $G$, $χ(G)$ denotes the chromatic number of $G$ and $ω(G)$ denotes the size of the largest clique in $G$. A hereditary class of graphs is called $χ$-bounded if there is a function $f$ such that for each graph $G$ in the class, $χ(G) \le f(ω(G))$. Scott (1997) conjectured that for every graph $H$, the class of graphs which do not contain any subdivision of $H$ as an induced subgraph is $χ$-bounded. He proved his conjecture when $H$ is a tree and when $H$ is the complete graph on four vertices, $K_4$. Esperet and Trotignon (2019) proved that the conjecture holds when $H$ is $K_4$ with one edge subdivided once. Scott's conjecture was disproved by Pawlik et al. (2014). Chalopin et al. (2016) gave more counterexamples including the graph obtained from $K_4$ by subdividing each edge of a 4-cycle once. We prove that the conjecture holds when $H$ consists of a complete bipartite graph with and additional vertex which has exactly two neighbours, on the same side of the bipartition. As a special case, this proves Scott's conjecture when $H$ is obtained from $K_4$ by subdividing two disjoint edges.
Fields of Study & Subjects
Advanced Graph Theory Research
Limits and Structures in Graph Theory
Advanced Topology and Set Theory
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 12 February 2026
- Language
- EN
- Document type
- Preprint