𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Stars and bonds in crossing-critical graphs

✍ Scribed by Petr Hliněný; Gelasio Salazar

Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
311 KB
Volume
65
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The structure of previous known infinite families of crossing‐critical graphs had led to the conjecture that crossing‐critical graphs have bounded bandwidth. If true, this would imply that crossing‐critical graphs have bounded degree, that is, that they cannot contain subdivisions of K~1, n~ for arbitrarily large n. In this article we prove two new results that revolve around this question. On the positive side, we show that crossing‐critical graphs cannot contain subdivisions of K~2, n~ for arbitrarily large n. On the negative side, we show that there are simple 3‐connected graphs with arbitrarily large maximum degree that are 2‐crossing‐critical in the projective plane. Although the former conjecture is now disproved in a subsequent manuscript by Dvořák and Mohar, our results are not affected, and some interesting questions remain. Namely, can the bandwidth conjecture still be true for simple 3‐connected graphs in the plane? © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 198–215, 2010

📜 SIMILAR VOLUMES

Nearly light cycles in embedded graphs a
Nearly light cycles in embedded graphs and crossing-critical graphs
✍ Mario Lomelí; Gelasio Salazar 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB

## Abstract We find a lower bound for the proportion of face boundaries of an embedded graph that are nearly light (that is, they have bounded length and at most one vertex of large degree). As an application, we show that every sufficiently large __k__‐crossing‐critical graph has crossing number a

Infinite families of crossing-critical g
Infinite families of crossing-critical graphs with prescribed average degree and crossing number
✍ Drago Bokal 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 242 KB 👁 1 views

## Abstract Širáň constructed infinite families of __k__‐crossing‐critical graphs for every __k__⩾3 and Kochol constructed such families of simple graphs for every __k__⩾2. Richter and Thomassen argued that, for any given __k__⩾1 and __r__⩾6, there are only finitely many simple __k__‐crossing‐criti

Long cycles in critical graphs
Long cycles in critical graphs
✍ Noga Alon; Michael Krivelevich; Paul Seymour 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 57 KB 👁 3 views
Independence and hamiltonicity in 3-domi
Independence and hamiltonicity in 3-domination-critical graphs
✍ Favaron, Odile; Tian, Feng; Zhang, Lei 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 3 views

Let δ, γ, i and α be respectively the minimum degree, the domination number, the independent domination number and the independence number of a graph G. The graph G is 3-γ-critical if γ = 3 and the addition of any edge decreases γ by 1. It was conjectured that any connected 3-γ-critical graph satisf