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

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00800048
Contributor : Nicolas Trotignon Connect in order to contact the contributor
Submitted on : Wednesday, March 13, 2013 - 10:12:39 AM
Last modification on : Thursday, September 29, 2022 - 2:58:07 PM

Links full text

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

42