𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Cyclic-order graphs and Zarankiewicz's crossing-number conjecture

✍ Scribed by D. R. Woodall

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
750 KB
Volume
17
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Zarankiewicz's conjecture, that the crossing number of the complete‐bipartite graph K~m, n~ is [1/2 m] [1/2 (m] −1) [1/2 n] [1/2 (n −1)], was proved by Kleitman when min(m, n) ≤ 6, but was unsettled in all other cases. The cyclic‐order graph CO__n__ arises naturally in the study of this conjecture; it is a vertex‐transitive harmonic diametrical (even) graph. In this paper the properties of cyclic‐order graphs are investigated and used as the basis for computer programs that have verified Zarankiewicz's conjecture for K~7,7~ and K~7,9~; thus the smallest unsettled cases are now K~7,11~ and K~9,9~. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

On graphs whose line graphs have crossin
On graphs whose line graphs have crossing number one
✍ Stanislav Jendrol'; Marián Kles̆c̆ 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB

## Abstract Necessary and sufficient conditions are given for a nonplanar graph to have a line graph with crossing number one. This corrects some errors in Kulli et al. 4. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 181–188, 2001

On Line Graphs with Crossing Number 1
On Line Graphs with Crossing Number 1
✍ V. R. Kulli; D. G. Akka; L. W. Beineke 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

## Abstract In this paper we deduce a necessary and sufficient condition for a line grah to have crossing number 1. In addition, we prove that the line graph of any nonplanar graph has crossing number greater than 2.

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