HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Excluding induced subdivisions of the bull and related graphs.

Abstract : For any graph H, let Forb*(H) be the class of graphs with no induced subdivision of H. It was conjectured in [J Graph Theory, 24 (1997), 297311] that, for every graph H, there is a function fH: N?R such that for every graph G epsilon Forb*(H), chi(G)<= fH(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.
Document type :
Journal articles
Complete list of metadata

Contributor : Nicolas Trotignon Connect in order to contact the contributor
Submitted on : Wednesday, March 13, 2013 - 10:12:39 AM
Last modification on : Wednesday, March 23, 2022 - 3:02:12 AM

Links full text




Maria Chudnovsky, Irena Penev, Alexander Scott, Nicolas Trotignon. Excluding induced subdivisions of the bull and related graphs.. Journal of Graph Theory, Wiley, 2012, 71 (1), pp.49-68. ⟨10.1002/jgt.20631⟩. ⟨ensl-00800048⟩



Record views