Class 1 Graph

 

Vizing's theorem states that a graph can be edge-colored in either  or  colors, where  is the maximum vertex degree of the graph. A graph with edge chromatic number equal to  is known as a class 1 graph.

König's line coloring theorem states that all bipartite graphs are class 1. All cubic Hamiltonian graphs are class 1, as are planar graphs with maximum vertex degree  (Cole and Kowalik 2008).

Class 1 graphs have both edge chromatic number and fractional edge chromatic number equal to .

Families of non-bipartite graphs that appear to be class 1 (or at least whose smallest members are all class 1) include king, Lindgren-Sousselier, and windmill graphs (S. Wagon, pers. comm., Oct. 27-28, 2011). Keller graphs are class 1 (Jarnicki et al. 2015). Aubert and Schneider (1982) showed that rook graphs admit Hamiltonian decomposition, meaning they are class 1 when they have even vertex count and class 2 when they have odd vertex count (because they are odd regular).

The numbers of simple class 1 graphs on , 2, ... nodes are 1, 2, 3, 10, 28, 145, ... (OEIS A099435).

Similarly, the numbers of simple connected class 1 graphs are 1, 1, 1, 6, 17, 109, 821, 11050, 260150, ... (OEIS A099436; Royle).

---

REFERENCES

Aubert, J. and Schneider, B. "Décomposition de la somme cartésienne d'un cycle et de l'union de deux cycles hamiltoniens en cycles hamiltoniens." Disc. Math. 38, 7-16, 1982.

Cole, R. and Kowalik, L. "New Linear-Time Algorithms for Edge-Coloring Planar Graphs." Algorithmica 50, 351-368, 2008.

Jarnicki, W.; Myrvold, W.; Saltzman, P.; and Wagon, S. "Properties, Proved and Conjectured, of Keller, Mycielski, and Queen Graphs." To appear in Ars Math. Comtemp. 2017.

Royle, G. "Class 2 Graphs." http://school.maths.uwa.edu.au/~gordon/remote/graphs/#class2.Sloane, N. J. A. Sequences A099435 and A099436 in "The On-Line Encyclopedia of Integer Sequences."

اخر الاخبار

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

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

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

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

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

المزيد

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

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

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

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

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

المزيد

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

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

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

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