𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A new proof of Grünbaum's 3 color theorem

✍ Scribed by O.V. Borodin

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
307 KB
Volume
169
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A simple proof of Grfinbaum's theorem on the 3-colourability of planar graphs having at most three 3-cycles is given, which does not employ the colouring extension.

In 1958, Gr6tzsch I-5] proved that every planar graph without cycles of length three is 3-colourable. In 1963, Griinbaum [6] extended this result as follows:

Theorem 1. Every planar graph with at most three 3-cycles is 3-colourable.

The number of 3-cycles is best possible due to K 4. Actually, GriJnbaum [6] got Theorem 1 as a corollary from the following statement:

Claim 2. Let G be a plane graph with faces only of length 3, 4, and 5. Then (a) /f in G there are at most three 3-cycles, then G is 3-colourable;

(b) /f in G there is at most one 3-cycle, then every 3-colouring of a face of G can be extended to a 3-colouring of G.

Claim 2 was included with the proof in the monographs [8, 9], but in 1972, Gallai discovered the counterexample presented in Fig.

📜 SIMILAR VOLUMES

Proof of a conjecture of Burr, Grünbaum,
Proof of a conjecture of Burr, Grünbaum, and Sloane
✍ Jacob E. Goodman 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 926 KB

We establish a duality principle for arrangements of pseudolines in the projective plane, and thereby prove the conjecture of Burr, Griinbaum, and Sloane that the solution T(p) of the "orchard problem" for pseudoline arrangements and the solution r(p) of the dual problem xe equa1.

A conjecture of Borodin and a coloring o
A conjecture of Borodin and a coloring of Grünbaum
✍ Dieter Rautenbach 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB

## Abstract In 1976, Borodin conjectured that every planar graph has a 5‐coloring such that the union of every __k__ color classes with 1 ≤ __k__ ≤ 4 induces a (__k__—1)‐degenerate graph. We prove the existence of such a coloring using 18 colors. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:139

A new proof of the 6 color theorem
A new proof of the 6 color theorem
✍ Oleg V. Borodin 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 579 KB

## Abstract In 1965 Ringel raised a 6 color problem for graphs that can be stated in at least three different forms. In particular, is it possible to color the vertices and faces of every plane graph with 6 colors so that any two adjacent or incident elements are colored differently? This 6 color p

A new proof of the colored Kruskal—Katon
A new proof of the colored Kruskal—Katona theorem
✍ Eran London 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 386 KB

An extension of the Kruskal-Katona theorem to colored hypergraphs was given by Frankl, Fiiredi and Kalai in [Shadows of colored complexes, Mathematics Scandinavica]. Here we give a new simple proof.

A new proof of menger's theorem
A new proof of menger's theorem
✍ Peter V. O'Neil 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 134 KB 👁 1 views

## Abstract A new proof of Menger's theorem is presented.