pith. sign in

arxiv: 1309.1312 · v1 · pith:M3QTXNUEnew · submitted 2013-09-05 · 🧮 math.CO

Excluding induced subdivisions of the bull and related graphs

classification 🧮 math.CO
keywords graphedgegraphsinducedmatchingbulleveryforb
0
0 comments X
read the original abstract

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 $f_H:\mathbb{N} \rightarrow \mathbb{R}$ such that for every graph $G \in {\rm Forb}^*(H)$, $\chi(G) \leq f_H(\omega(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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.