✦ LIBER ✦

Crossing numbers of sequences of graphs II: Planar tiles

✍ Scribed by Benny Pinontoan; R. Bruce Richter

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 105 KB
Volume: 42
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10097

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We describe a method of creating an infinite family of crossing‐critical graphs from a single small planar map, the tile, by gluing together many copies of the tile together in a circular fashion. This method yields all known infinite families of k‐crossing‐critical graphs. Furthermore, the method yields new infinite families, which extend from (4,6) to (3.5,6) the interval of rationals r for which there is, for some k, an infinite sequence of k‐crossing‐critical graphs all having average degree r. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 332–341, 2003

📜 SIMILAR VOLUMES

Crossing numbers of imbalanced graphs

✍ János Pach; József Solymosi; Gábor Tardos 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 103 KB

## Abstract The __crossing number__, cr(__G__), of a graph __G__ is the least number of crossing points in any drawing of __G__ in the plane. According to the Crossing Lemma of M. Ajtai, V. Chvátal, M. Newborn, E. Szemerédi, Theory and Practice of Combinatorics, North‐Holland, Amsterdam, New York,

Domination numbers of planar graphs

✍ MacGillivray, G.; Seyffarth, K. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 967 KB

The problem of determining the domination number of a graph is a well known NPhard problem, even when restricted to planar graphs. By adding a further restriction on the diameter of the graph, we prove that planar graphs with diameter two and three have bounded domination numbers. This implies that

Crossing numbers of Sierpiński-like grap

Crossing numbers of Sierpiński-like graphs

✍ Sandi Klavžar; Bojan Mohar 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB

## Abstract Crossing numbers of Sierpiński graphs __S__(__n__,__k__) and their regularizations __S__^+^(__n__,__k__) and __S__^++^(__n__,__k__) are studied. Drawings of these graphs are presented and proved to be optimal for __S__^+^(__n__,__k__) and __S__^++^(__n__,__k__) for every __n__ ≥ 1 and _

Star chromatic numbers of some planar gr

Star chromatic numbers of some planar graphs

✍ Gao, Guogang; Wang, Yiju; Zhou, Huishan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB 👁 2 views

The concept of the star chromatic number of a graph was introduced by Vince (A. Vince, Star chromatic number, J. Graph Theory 12 (1988), 551--559), which is a natural generalization of the chromatic number of a graph. This paper calculates the star chromatic numbers of three infinite families of pla

The star-chromatic number of planar grap

The star-chromatic number of planar graphs

✍ Moser, David 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 2 views

The star-chromatic number of a graph, a parameter introduced by Vince, is a natural generalization of the chromatic number of a graph. Here we construct planar graphs with star-chromatic number r, where r is any rational number between 2 and 3, partially answering a question of Vince.

The Game Coloring Number of Planar Graph

The Game Coloring Number of Planar Graphs

✍ Xuding Zhu 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 121 KB

This paper discusses a variation of the game chromatic number of a graph: the game coloring number. This parameter provides an upper bound for the game chromatic number of a graph. We show that the game coloring number of a planar graph is at most 19. This implies that the game chromatic number of a