✦ LIBER ✦

Compact topological minors in graphs

✍ Scribed by Tao Jiang

Publisher: John Wiley and Sons
Year: 2010
Tongue: English
Weight: 155 KB
Volume: 67
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20522

No coin nor oath required. For personal study only.

✦ Synopsis

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 refines the main result in [A. Kostochka and Pyber, Combinatorica 8 (1988), 83-86] and resolves an open question raised there. We also pose some questions.

📜 SIMILAR VOLUMES

Topological Minors in Graphs of Large Gi

Topological Minors in Graphs of Large Girth

✍ Daniela Kühn; Deryk Osthus 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 204 KB

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 fal

Complete minors in pseudorandom graphs

✍ Andrew Thomason 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 64 KB 👁 1 views

Clique Minors in Graphs and Their Comple

Clique Minors in Graphs and Their Complements

✍ Bruce Reed; Robin Thomas 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 107 KB

A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. Let t 1 be an integer, and let G be a graph on n vertices with no minor isomorphic to K t+1 . Kostochka conjectures that there exists a constant c=c(t) independent of G such that the complement of G has

Joint Continuity and Compactness for a G

Joint Continuity and Compactness for a Graph Topology in General Function Spaces

✍ Harry Poppe 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 256 KB

On Ks,t minors in (s+t)-chromatic graphs

✍ A. V. Kostochka 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB

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