𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Infinite families of 4-chromatic Grötzsch-Sachs graphs

✍ Scribed by Andrey A. Dobrynin; Leonid S. Mel'nikov

Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
215 KB
Volume
59
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G be a 4‐regular planar graph and suppose that G has a cycle decomposition S (i.e., each edge of G is in exactly one cycle of the decomposition) with every pair of adjacent edges on a face always in different cycles of S. Such graphs, called Grötzsch‐Sachs graphs, arise as a superposition of simple closed curves in the plane with tangencies disallowed. The first two known 4‐chromatic Grötzsch‐Sachs graphs of order 18 were reported in Dobrynin and Mel'nikov [Discrete Math 306 (2006), 591‐594]. In this article, all edge 4‐critical subgraphs of these graphs are described and infinite families of 4‐chromatic Grötzsch‐Sachs graphs with connectivity 2, 3, and 4 are constructed. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 279–292, 2008

📜 SIMILAR VOLUMES

On chromatic uniqueness of two infinite
On chromatic uniqueness of two infinite families of graphs
✍ Feng-Ming Dong 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 229 KB 👁 1 views

## Abstract In this paper, it is proven that for each __k__ ≥ 2, __m__ ≥ 2, the graph Θ~__k__~(__m,…,m__), which consists of __k__ disjoint paths of length __m__ with same ends is chromatically unique, and that for each __m, n__, 2 ≤ __m__ ≤ __n__, the complete bipartite graph __K__~__m,n__~ is chr

The fractional chromatic number of infin
The fractional chromatic number of infinite graphs
✍ Imre Leader 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 398 KB 👁 1 views

## Abstract The fractional chromatic number of a graph __G__ is the infimum of the total weight that can be assigned to the independent sets of __G__ in such a way that, for each vertex __v__ of __G__, the sum of the weights of the independent sets containing __v__ is at least 1. In this note we g

Note on Infinite Families of Trivalent S
Note on Infinite Families of Trivalent Semisymmetric Graphs
✍ Seymour Lipschutz; Ming-Yao Xu 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 60 KB

A simple undirected graph is said to be semisymmetric if it is regular and edge-transitive but not vertex-transitive. This paper uses the groups PSL(2, p) and PGL(2, p), where p is a prime, to construct two new infinite families of trivalent semisymmetric graphs.

Size ramsey numbers of stars versus 4-ch
Size ramsey numbers of stars versus 4-chromatic graphs
✍ Oleg Pikhurko 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 124 KB 👁 1 views

## Abstract We investigate the asymptotics of the size Ramsey number __î__(__K__~1,__n__~__F__), where __K__~1,__n__~ is the __n__‐star and __F__ is a fixed graph. The author 11 has recently proved that __r̂__(__K__~1,n~,__F__)=(1+__o__(1))__n__^2^ for any __F__ with chromatic number χ(__F__)=3. He

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