 |
 |
 |
 |
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.
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 : Wednesday, March 23, 2022 - 3:02:12 AM
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
