𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Construction of crossing-critical graphs

✍ Scribed by Martin Kochol

Book ID
103057383
Publisher
Elsevier Science
Year
1987
Tongue
English
Weight
145 KB
Volume
66
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is crossing-critical if deleting any edge decreases its crossing number on the plane. For any n >I 2 we present a construction of an infinite family of 3-connected crossing-critical graphs with crossing number n.

📜 SIMILAR VOLUMES

Stars and bonds in crossing-critical gra
Stars and bonds in crossing-critical graphs
✍ Petr Hliněný; Gelasio Salazar 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 311 KB

## 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 __

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

A construction of chromatic index critic
A construction of chromatic index critical graphs
✍ Hian Poh Yap 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

## Abstract We prove that if __K__ is an undirected, simple, connected graph of even order which is of class one, regular of degree __p__ ≥ 2 and such that the subgraph induced by any three vertices is either connected or null, then any graph __G__ obtained from __K__ by splitting any vertex is __p

Haj�s constructions of critical graphs
Haj�s constructions of critical graphs
✍ Jensen, Tommy R.; Royle, Gordon F. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 365 KB 👁 1 views

For every k ≥ 4 there exists a k-critical graph that is not Hajós-kconstructible through a sequence of k-critical graphs. This completely answers a question of G. Hajós, which has been answered previously only for k = 8 with an example given by P. Catlin. Also the corresponding problem for Ore's con