Excluding induced subdivisions of the bull and related graphs

Maria Chudnovsky, Irena Penev, Alex Scott, Nicolas Trotignon

Research output: Contribution to journalArticle

2 Scopus citations

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 fH: ℕ→ℝ 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 languageEnglish (US)
Pages (from-to)49-68
Number of pages20
JournalJournal of Graph Theory
Volume71
Issue number1
DOIs
StatePublished - Sep 2012
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

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

Fingerprint Dive into the research topics of 'Excluding induced subdivisions of the bull and related graphs'. Together they form a unique fingerprint.

  • Cite this