Excluding induced subdivisions of the bull and related graphs. - Archive ouverte HAL Access content directly
Journal Articles Journal of Graph Theory Year : 2012

Excluding induced subdivisions of the bull and related graphs.

(1) , (1) , (2) , (3)
1
2
3

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.

Dates and versions

ensl-00800048 , version 1 (13-03-2013)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More