✦ LIBER ✦

6-regular 4-critical graph

✍ Scribed by A. V. Pyatkin

Publisher: John Wiley and Sons
Year: 2002
Tongue: English
Weight: 70 KB
Volume: 41
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10066

No coin nor oath required. For personal study only.

✦ Synopsis

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

📜 SIMILAR VOLUMES

Regular 4-critical graphs of even degree

✍ Andrey A. Dobrynin; Leonid S. Melnikov; Artem V. Pyatkin 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 237 KB 👁 1 views

## 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‐transiti

P4-decompositions of regular graphs

✍ Heinrich, Katherine; Liu, Jiping; Yu, Minli 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB 👁 1 views

In this article, we show that every simple r-regular graph G admits a balanced P 4 -decomposition if r ≡ 0(mod 3) and G has no cut-edge when r is odd. We also show that a connected 4-regular graph G admits a P 4 -decomposition if and only if |E(G)| ≡ 0(mod 3) by characterizing graphs of maximum degr

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.

Regular factors of regular graphs

✍ B. Bollobás; Akira Saito; N. C. Wormald 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 242 KB

Given r 3 3 and 1 s A s r, we determine all values of k for which every r-regular graph with edge-connectivity A has a k-factor. Some of the earliest results in graph theory are due to Petersen [8] and concern factors in graphs. Among others, Petersen proved that a regular graph of even degree has a

From regular boundary graphs to antipoda

From regular boundary graphs to antipodal distance-regular graphs

✍ Fiol, M. A.; Garriga, E.; Yebra, J. L. A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 383 KB 👁 2 views

Let Γ be a regular graph with n vertices, diameter D, and d + 1 In a previous paper, the authors showed that if P (λ) > n -1, then D ≤ d -1, where P is the polynomial of degree d-1 which takes alternating values ±1 at λ 1 , . . . , λ d . The graphs satisfying P (λ) = n -1, called boundary graphs, h

Covering Regular Graphs

✍ Jan Kratochvı́l; Andrzej Proskurowski; Jan Arne Telle 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 365 KB

A covering projection from a graph G onto a graph H is a ``local isomorphism'': a mapping from the vertex set of G onto the vertex set of H such that, for every v # V(G), the neighborhood of v is mapped bijectively onto the neighborhood (in H ) of the image of v. We investigate two concepts that con