✦ LIBER ✦

On a Crossing Number Result of Richter and Thomassen

✍ Scribed by Gelasio Salazar

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 67 KB
Volume: 79
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1999.1943

No coin nor oath required. For personal study only.

✦ Synopsis

We show that if G is a graph minimal with respect to having crossing number at least k, and G has no vertices of degree 3, then G has crossing number at most 2k+35.

2000 Academic Press

Richter and Thomassen proved that if G is minimal with respect to having crossing number at least k, then the crossing number cr(G) of G is at most 2.5k+16 [1]. Our aim in this note is to observe that if G has no vertices of degree 3, then the proportionality constant in this bound can be improved to 2.

📜 SIMILAR VOLUMES

On a conjecture of Thomassen and Toft

✍ Kriesell, Matthias 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB 👁 2 views

This article is motivated by a conjecture of Thomassen and Toft on the number s 2 (G) of separating vertex sets of cardinality 2 and the number v 2 (G) of vertices of degree 2 in a graph G belonging to the class G of all 2-connected graphs without nonseparating induced cycles. Let G denote the numbe

The crossing number of c4 × c4

✍ Alice M. Dean; R. Bruce Richter 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 210 KB

We prove t h a t t h e crossing number of C4 X Ca is 8.

The crossing number of K11 is 100

✍ Shengjun Pan; R. Bruce Richter 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB

## Abstract The crossing number of __K~n~__ is known for __n__ ⩽ 10. We develop several simple counting properties that we shall exploit in showing by computer that __cr__(__K__~11~ = 100, which implies that __cr__(__K__~12~) = 150. We also determine the numbers of non‐isomorphic optimal drawings o

The crossing number ofK3,n in a surface

✍ Richter, R. Bruce; ?ir�?, J. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB

In this article, w e show that the crossing number of K3," in a surface with Euler genus . This generalizes a result of Guy and Jenkyns, who obtained this result for the torus. 0

On 3-regular graphs having crossing numb

On 3-regular graphs having crossing number at least 2

✍ Dan McQuillan; R. Bruce Richter 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 414 KB

## Abstract We give a planar proof of the fact that if __G__ is a 3‐regular graph minimal with respect to having crossing number at least 2, then the crossing number of __G__ is 2.

The Crossing Number of a Graph on a Comp

The Crossing Number of a Graph on a Compact 2-Manifold

✍ F. Shahrokhi; O. Sýkora; L.A. Székely; I. Vrťo 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 478 KB

We introduce a general framework to estimate the crossing number of a graph on a compact 2-manifold in terms of the crossing number of the complete graph of the same size on the same manifold. The bounds are tight within a constant multiplicative factor for many graphs, including hypercubes, some co