✦ LIBER ✦

On nearly regular co-critical graphs

✍ Scribed by Tibor Szabó

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 136 KB
Volume: 160
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00121-c

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is called (K 3, K3)-co-critical if the edges of G can be coloured with two colours without getting a monochromatic triangle, but adding any new edge to the graph, this kind of 'good' colouring is impossible. In this short note we construct (K 3, K3)-co-critical graphs of maximal degree O(n3/4).

📜 SIMILAR VOLUMES

Regular factors in nearly regular graphs

✍ Jean-Claude Bermond; Michel Las Vergnas 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 232 KB

Greedy Construction of Nearly Regular Gr

Greedy Construction of Nearly Regular Graphs

✍ G.O.H. Katona; Á. Seress 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 560 KB

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

Nearly light cycles in embedded graphs a

Nearly light cycles in embedded graphs and crossing-critical graphs

✍ Mario Lomelí; Gelasio Salazar 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB

## Abstract We find a lower bound for the proportion of face boundaries of an embedded graph that are nearly light (that is, they have bounded length and at most one vertex of large degree). As an application, we show that every sufficiently large __k__‐crossing‐critical graph has crossing number a

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

On End-regular graphs

✍ Suohai Fan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 390 KB

A graph X is End-regular if its endomorphism monoid End X is regular in the sernigroup sense, that is, for any fin End X there exists g in End X with fgf=f. End-regular bipartite graphs were characterized in [l]. In this paper, End-regular graphs are obtained through the lexicographic product of End