Excluding induced subdivisions of the bull and related graphs

Maria Chudnovsky; Irena Penev; Alex Scott; Nicolas Trotignon

doi:10.1002/jgt.20631

Excluding induced subdivisions of the bull and related graphs

Maria Chudnovsky, Irena Penev, Alex Scott, Nicolas Trotignon

Research output: Contribution to journal › Article › peer-review

3 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 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	https://doi.org/10.1002/jgt.20631
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

Access to Document

10.1002/jgt.20631

Cite this

@article{134b120c7dce4b01871c246267fdb0f6,

title = "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 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.",

keywords = "bull, chi-bounded, coloring, induced subgraphs, necklace",

author = "Maria Chudnovsky and Irena Penev and Alex Scott and Nicolas Trotignon",

year = "2012",

month = sep,

doi = "10.1002/jgt.20631",

language = "English (US)",

volume = "71",

pages = "49--68",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - Excluding induced subdivisions of the bull and related graphs

AU - Chudnovsky, Maria

AU - Penev, Irena

AU - Scott, Alex

AU - Trotignon, Nicolas

PY - 2012/9

Y1 - 2012/9

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

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

KW - bull

KW - chi-bounded

KW - coloring

KW - induced subgraphs

KW - necklace

UR - http://www.scopus.com/inward/record.url?scp=84864489390&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84864489390&partnerID=8YFLogxK

U2 - 10.1002/jgt.20631

DO - 10.1002/jgt.20631

M3 - Article

AN - SCOPUS:84864489390

SN - 0364-9024

VL - 71

SP - 49

EP - 68

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

Excluding induced subdivisions of the bull and related graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this