✦ LIBER ✦

Excluding Induced Subdivisions of the Bull and Related Graphs

✍ Scribed by Maria Chudnovsky; Irena Penev; Alex Scott; Nicolas Trotignon

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 233 KB
Volume: 71
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20631

No coin nor oath required. For personal study only.

✦ Synopsis

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. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:49–68, 2012

📜 SIMILAR VOLUMES

Subdivisions of large complete bipartite

Subdivisions of large complete bipartite graphs and long induced paths in k-connected graphs

✍ Thomas Böhme; Bojan Mohar; Riste Škrekovski; Michael Stiebitz 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 67 KB 👁 1 views

## Abstract It is proved that for every positive integers __k__, __r__ and __s__ there exists an integer __n__ = __n__(__k__,__r__,__s__) such that every __k__‐connected graph of order at least __n__ contains either an induced path of length __s__ or a subdivision of the complete bipartite graph __

Subdivisions and the chromatic index of

Subdivisions and the chromatic index of r-graphs

✍ K. Kilakos; F. B. Shepherd 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 625 KB

Let T2 be the graph obtained from the Petersen graph by first deleting a vertex and then contracting an edge incident to a vertex of degree two. We give a simple characterization of the graphs that contain no subdivision of T2. This characterization is used to show that if every planar r-graph is r-

On the Complexity of Recognizing Hamming

On the Complexity of Recognizing Hamming Graphs and Related Classes of Graphs

✍ Wilfried Imrich; Sandi Klavzar 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 287 KB

The relation of the sciatic nerve and of

The relation of the sciatic nerve and of its subdivisions to the piriformis muscle

✍ Beaton, Lindsay E. ;Anson, Barry J. 📂 Article 📅 1937 🏛 John Wiley and Sons 🌐 English ⚖ 248 KB 👁 2 views

Orientations of Self-complementary Graph

Orientations of Self-complementary Graphs and the Relation of Sperner and Shannon Capacities

✍ A. Sali; G. Simonyi 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 81 KB

We prove that the edges of a self-complementary graph and its complement can be oriented in such a way that they remain isomorphic as digraphs and their union is a transitive tournament. This result is used to explore the relation between the Shannon and Sperner capacity of certain graphs. In partic

A linear Vizing-like relation relating t

A linear Vizing-like relation relating the size and total domination number of a graph

✍ Michael A. Henning 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 77 KB

## Abstract We prove that __m__ ≤ Δ (__n__ − γ~t~) for every graph each component of which has order at least 3 of order __n__, size __m__, total domination number γ~t~, and maximum degree Δ ≥ 3. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 285–290, 2005