Journal article icon

Journal article

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), 297-311] that, for every graph H, there is a function f H: ℕ→ℝ such that for every graph G∈Forb*(H), Χ(G) ≤ f H(ω(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 m...

Expand abstract

Actions


Access Document


Publisher copy:
10.1002/jgt.20631

Authors


Chudnovsky, M More by this author
Trotignon, N More by this author
Journal:
Journal of Graph Theory
Volume:
71
Issue:
1
Pages:
49-68
Publication date:
2012-09-05
DOI:
EISSN:
1097-0118
ISSN:
0364-9024
URN:
uuid:a3d34db1-1b7d-4143-992e-043ce4c13786
Source identifiers:
395904
Local pid:
pubs:395904
Language:
English
Keywords:

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP