𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Regular 4-critical graphs of even degree

✍ Scribed by Andrey A. Dobrynin; Leonid S. Melnikov; Artem V. Pyatkin

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
237 KB
Volume
46
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In 1960, Dirac posed the conjecture that r‐connected 4‐critical graphs exist for every r ≥ 3. In 1989, Erdős conjectured that for every r ≥ 3 there exist r‐regular 4‐critical graphs. In this paper, a technique of constructing r‐regular r‐connected vertex‐transitive 4‐critical graphs for even r ≥ 4 is presented. Such graphs are found for r = 6, 8, 10. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 103–130, 2004

📜 SIMILAR VOLUMES

6-regular 4-critical graph
6-regular 4-critical graph
✍ A. V. Pyatkin 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 70 KB

## Abstract P. Erdős conjectured in [2] that __r__‐regular 4‐critical graphs exist for every __r__ ≥ 3 and noted that no such graphs are known for __r__ ≥ 6. This article contains the first example of a 6‐regular 4‐critical graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 286–291, 2002

Factorizations of regular graphs of high
Factorizations of regular graphs of high degree
✍ A. J. W. Hilton 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB 👁 1 views

A p-factor of a graph G is a regular spanning subgraph of degree p . For G regular of degree d ( G ) and order 2n, let ( p l , ..., p,) be a partition of d ( G ) , so that p i > 0 ( I S i S r ) and p , i i pr = d(G). If H I . ..., H, are edge-disjoint regular spanning subgraphs of G of degrees p I ,

Chromatic-index-critical graphs of even
Chromatic-index-critical graphs of even order
✍ Gr�newald, Stefan; Steffen, Eckhard 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 298 KB 👁 2 views

A k-critical (multi-) graph G has maximum degree k, chromatic index χ (G) = k + 1, and χ (G -e) < k + 1 for each edge e of G. For each k ≥ 3, we construct k-critical (multi-) graphs with certain properties to obtain counterexamples to some well-known conjectures.

Generating all planer graphs regular of
Generating all planer graphs regular of degree four
✍ Paolo Manca 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 225 KB 👁 1 views

## Abstract All planar connected graphs regular of degree four can be generated from the graph of the octahedron, using four operations.

Number of labeled 4-regular graphs
Number of labeled 4-regular graphs
✍ R. C. Read; N. C. Wormald 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 305 KB

## Abstract Several operations on 4‐regular graphs and pseudographs are analyzed and equations are obtained relating the numbers of these graphs on given numbers of labeled points. These equations are used recursively to find the numbers of 4‐regular graphs on up to 13 labeled points.