✦ LIBER ✦

Topological Minors in Graphs of Large Girth

✍ Scribed by Daniela Kühn; Deryk Osthus

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 204 KB
Volume: 86
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2002.2133

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that every graph of minimum degree at least r and girth at least 186 contains a subdivision of K rþ1 and that for r5435 a girth of at least 15 suffices. This implies that the conjecture of Haj ! o os that every graph of chromatic number at least r contains a subdivision of K r (which is false in general) is true for graphs of girth at least 186 (or 15 if r5436). More generally, we show that for every graph H of maximum degree DðH Þ52; every graph G of minimum degree at least maxfDðHÞ; 3g and girth at least 166 log jH j log DðH Þ contains a subdivision of H: This bound on the girth of G is best possible up to the value of the constant and improves a result of Mader, who gave a bound linear in jH j: # 2002 Elsevier Science (USA)

📜 SIMILAR VOLUMES

Compact topological minors in graphs

✍ Tao Jiang 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB

Let be a real number such that 0< < 1 2 and t a positive integer. Let n be a sufficiently large positive integer as a function of t and . We show that every n-vertex graph with at least n 1+ edges contains a subdivision of K t in which each edge of K t is subdivided less than 10 / times. This refine

Domination number of cubic graphs with l

Domination number of cubic graphs with large girth

✍ Daniel Král'; Petr Škoda; Jan Volec 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

We show that every n-vertex cubic graph with girth at least g have domination number at most 0.299871n+O(n / g) < 3n / 10+O(n / g) This research was done when the Petr Škoda was a student of

Total Colourings of Planar Graphs with L

Total Colourings of Planar Graphs with Large Girth

✍ O.V. Borodin; A.V. Kostochka; D.R. Woodall 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 96 KB

It is proved that if G is a planar graph with total (vertex-edge) chromatic number χ , maximum degree and girth g, then χ = + 1 if ≥ 5 and g ≥ 5, or ≥ 4 and g ≥ 6, or ≥ 3 and g ≥ 10. These results hold also for graphs in the projective plane, torus and Klein bottle.

Minors in large almost-5-connected non-p

Minors in large almost-5-connected non-planar graphs

✍ Ken-Ichi Kawarabayashi; John Maharry 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 196 KB

## Abstract It is shown that every sufficiently large almost‐5‐connected non‐planar graph contains a minor isomorphic to an arbitrarily large graph from one of six families of graphs. The graphs in these families are also almost‐5‐connected, by which we mean that they are 4‐connected and all 4‐sepa

(2 + ?)-Coloring of planar graphs with l

(2 + ?)-Coloring of planar graphs with large odd-girth

✍ Klostermeyer, William; Zhang, Cun Quan 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB 👁 3 views

The odd-girth of a graph is the length of a shortest odd circuit. A conjecture by Pavol Hell about circular coloring is solved in this article by showing that there is a function f ( ) for each : 0 < < 1 such that, if the odd-girth of a planar graph G is at least f ( ), then G is (2 + )-colorable. N

On a Conjecture about Trees in Graphs wi

On a Conjecture about Trees in Graphs with Large Girth

✍ Tao Jiang 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 169 KB

The girth of a graph G is the length of a shortest cycle in G. Dobson (1994, Ph.D. dissertation, Louisiana State University, Baton Rouge, LA) conjectured that every graph G with girth at least 2t+1 and minimum degree at least kÂt contains every tree T with k edges whose maximum degree does not excee