Kempe Chain

Let  be a planar graph whose vertices have been properly colored and suppose  is colored . Define the -Kempe chain containing  to be the maximal connected component of  that

1. Contains , and

2. Contains only vertices that are colored with elements from 

(Gethner and Springer 2003).

A number of small graphs (with  the vertex count) that tangle the chains in Kempe's algorithm and so provide examples of how Kempe's supposed proof of the four-color theorem fails are illustrated above and summarized in the following table.

	graph name
9	Fritsch graph
9	Soifer graph
15	Poussin graph
17	Errera graph
23	Kittell graph
25	Heawood four-color graph

Interestingly, a number of these examples (though not the Soifer graph, which contains a 4-cycle) correspond to the skeletons of (possibly degenerate) deltahedra (E. Weisstein, Mar. 7, 2022). In particular, the Fritsch graph is the skeleton of the triaugmented triangular prism and the Errera graph is the skeleton of two pentagon-adjoined gyroelongated pentagonal pyramids.

---

REFERENCES

Gethner, E. and Springer, W. M. II. "How False Is Kempe's Proof of the Four-Color Theorem?" Congr. Numer. 164, 159-175, 2003.

Hutchinson, J. P. and Wagon, S. "Kempe Revisited." Amer. Math. Monthly 105, 170-174, 1998.Wagon, S. Mathematica in Action, 2nd ed. New York: Springer-Verlag, pp. 535-536, 1999.

اخر الاخبار

اخبار العتبة العباسية المقدسة

جمعية كشافة الكفيل: المجالس الحسينية تعلّم الفتية قيم نهضة الإمام الحسين (عليه السلام)

عَبرَ المجالس الحسينية.. المجمَع العلمي يقدّم محاضرات دينية وتلاوات قرآنية في بغداد والنجف وميسان

برعاية العتبة العباسية المقدسة.. موكب قناديل السماء يُحيي مراسم اليوم الثالث عشر من المحرّم

بعد انتهاء مراسم ذكرى دفن الأجساد الطاهرة قسم رعاية الصحن يباشر بحملة تنظيف واسعة لصحن مرقد أبي الفضل العباس (عليه السلام)

المزيد

الآخبار الصحية

لكبح الجوع وخسارة الوزن.. "سر بسيط" في نظام جوكوفيتش ؟

هل يساعد الرجيم في علاج الأمراض العقلية؟

لحماية أسنان طفلك.. هذا الفيتامين يقلل خطر التسوس

أكل الطعام بسرعة.. طريق سريع إلى أمراض خطيرة

المزيد

الآخبار التكنلوجية

ما هي أفضل درجة حرارة لتكييف الهواء في السيارة؟

ذوبان الأنهار الجليدية يوقظ "عمالقة نائمة"!

9 يوليو يشهد أقصر يوم في التاريخ المسجل ؟!!

راتبه عشرات ملايين الدولارات.. زوكربرغ يخطف "عقل أبل"

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength