✦ LIBER ✦

An improvement of the crossing number bound

✍ Scribed by Bernard Montaron

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 194 KB
Volume: 50
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20090

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The crossing number cr(G) of a simple graph G with n vertices and m edges is the minimum number of edge crossings over all drawings of G on the ℝ^2^ plane. The conjecture made by Erdős in 1973 that cr(G) ≥ Cm^3^/n^2^ was proved in 1982 by Leighton with C = 1/100 and this constant was gradually improved to reach the best known value C = 1/31.08 obtained recently by Pach, Radoicčić, Tardos, and Tóth [4] for graphs such that m ≥ 103n/16. We improve this result with values for the constant in the range 1/31.08 ≤ C &< 1/15 where C depends on m/n^2^. For example, C > 1/25 for graphs with m/n^2^ > 0.291 and n > 22, and C > 1/20 for dense graphs with m/n^2^ ≥ 0.485. © 2005 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

An improved upper bound on the crossing

An improved upper bound on the crossing number of the hypercube

✍ Luerbio Faria; Celina Miraglia Herrera de Figueiredo; Ondrej Sýkora; Imrich Vrt' 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB

## Abstract We draw the __n__‐dimensional hypercube in the plane with ${5\over 32}4^{n}-\lfloor{{{{n}^{2}+1}\over 2}}\rfloor {2}^{n-2}$ crossings, which improves the previous best estimation and coincides with the long conjectured upper bound of Erdös and Guy. © 2008 Wiley Periodicals, Inc. J Graph

An improved bound for the strong chromat

An improved bound for the strong chromatic number

✍ P. E. Haxell 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 156 KB 👁 1 views

## Abstract Let η > 0 be given. Then there exists __d__~0~ = __d__~0~(η) such that the following holds. Let __G__ be a finite graph with maximum degree at most __d__ ≥ __d__~0~ whose vertex set is partitioned into classes of size α __d__, where α≥ 11/4 + η. Then there exists a proper coloring of __

A lower bound for the crossing number of

A lower bound for the crossing number of Cm × Cn

✍ Gelasio Salazar 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 67 KB 👁 3 views

An improved edge bound on the interval n

An improved edge bound on the interval number of a graph

✍ Jeremy R. Spinrad; G. Vijayan; Douglas B. West 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB 👁 2 views

The upper bound on the interval number of a graph in terms of its number of edges is improved. Also, the interval number of graphs in hereditary classes is bounded in terms of the vertex degrees. A representation of a graph as an intersection graph assigns each vertex a set such that vertices are a

An Improvement of the Boshier-Nomura Bou

An Improvement of the Boshier-Nomura Bound

✍ A. Hiraki 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 93 KB

We show that the number of columns $\left(c_{i}, a_{i}, b_{i}\right)=(1,1, k-2)$ in the intersection arrays of distance-regular graphs is at most three if the column $(1,0, k-1)$ exists. This improves the Bosheir-Nomura bound from four to three. 1994 Academic Press, Inc.

Improved bounds for the chromatic number

Improved bounds for the chromatic number of a graph

✍ S. Louis Hakimi; Edward Schmeichel 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 2 views

## Abstract After giving a new proof of a well‐known theorem of Dirac on critical graphs, we discuss the elegant upper bounds of Matula and Szekeres‐Wilf which follow from it. In order to improve these bounds, we consider the following fundamental coloring problem: given an edge‐cut (__V__~1~, __V_