## 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 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.

Original language | English (US) |
---|---|

Pages (from-to) | 49-68 |

Number of pages | 20 |

Journal | Journal of Graph Theory |

Volume | 71 |

Issue number | 1 |

DOIs | |

State | Published - Sep 2012 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Geometry and Topology
- Discrete Mathematics and Combinatorics

## Keywords

- bull
- chi-bounded
- coloring
- induced subgraphs
- necklace