2013/09/05 by Maria Chudnovsky, Irena Penev, Alexander Scott +1 · 1 citation
Mathematics · #math.CO #msc:05C75
paper · pdf · doi:10.1002/jgt.20631
published as Journal of Graph Theory, 71:49-68, 2012
arxiv created 2013/09/05 · arxiv updated 2013/09/06
For any graph H, let \rm Forb^*(H) be the class of graphs with no induced subdivision of H. It was conjectured in [A.D. Scott, Induced trees in graphs of large chromatic number, \em Journal of Graph Theory, 24:297--311, 1997] that, for every graph H, there is a function fH:ℕ → ℝ such that for every graph G ∈ \rm Forb^*(H), χ(G) ≤ fH(ω(G)). We prove this conjecture for several graphs H, namely the paw (a triangle with a pendant edge), the bull (a triangle with two vertex-disjoint pendant edges), and what we call a "necklace," that is, a graph obtained from a path by choosing a matching such that no edge of the matching is incident with an endpoint of the path, and for each edge of the matching, adding a vertex adjacent to the ends of this edge.