Class 2 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 2 graph.

Class 2 graphs include the Petersen graph, complete graphs  for , 5, 7, ..., and the snarks.

All non-empty regular graphs with an odd number of nodes  are class 2 by parity. Such graphs automatically have an even number of edges per vertex.

A graph is trivially class 2 if the maximum independent edge sets are not large enough to cover all edges. In particular, a graph  is trivially class 2 if

where  is the matching number,  the maximum vertex degree, and  the edge count of .

The following table summarizes some named class 2 graphs.

graph
triangle graph	3
pentatope graph	5
Petersen graph	10
first Blanuša snark	18
second Blanuša snark	18
Robertson graph	19
flower snark	20
25-Grünbaum graph	25
Doyle graph	27
double star snark	30
Szekeres snark	50
McLaughlin graph	275

The numbers of simple class 2 graphs on , 2, ... nodes are 0, 0, 1, 1, 6, 11, 50, 131, 1131, ... (OEIS A099437).

Similarly, the numbers of simple connected class 2 graphs are 0, 0, 1, 0, 4, 3, 32, 67, 930, ... (OEIS A099438; Royle).

---

REFERENCES

Royle, G. "Class 2 Graphs." http://school.maths.uwa.edu.au/~gordon/remote/graphs/#class2.

Sloane, N. J. A. Sequences A099437 and A099438 in "The On-Line Encyclopedia of Integer Sequences."

اخر الاخبار

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

لزيادة المساحات الخضراء.. قسم الحزام الأخضر الثاني يشرع بحملة تشجير في جامعة العميد

اللجنة التحضيرية لمهرجان روح النبوة تعلن تمديد موعد تسلم البحوث الخاصة بالمسابقة البحثية

المجمع العلمي يطلق جلستين قرآنيتين لطلبة العلوم الدينية في النجف

قسم الشؤون الفكرية يقدم محاضرة حول أساليب الحوار الإيجابي لوفد شبابي من البصرة

المزيد

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

هل ممارسة الرياضة على معدة فارغة تحرق الدهون أكثر؟

العلم يوضح الوقت "الأمثل" لشرب القهوة

دراسة: "طريقة سهلة" لحماية رئتيك من آثار تلوث الهواء

بالذكاء الاصطناعي.. أداة جديدة لتحسين علاج الصرع عند الأطفال

المزيد

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

إيلون ماسك يعتزم إطلاق "غروكيبيديا" كمنافس لـ "ويكيبيديا"

"قرار" من أبل لحماية هواتف آيفون 17 من الخدوش

ميزة جديدة على "تشات جي بي تي".. شراء المنتجات من المحادثة

الصين تكشف عن توربين رياح طائر يغير قواعد الطاقة المتجددة

المزيد

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

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