Edge Chromatic Number

The edge chromatic number, sometimes also called the chromatic index, of a graph  is fewest number of colors necessary to color each edge of  such that no two edges incident on the same vertex have the same color. In other words, it is the number of distinct colors in a minimum edge coloring.

The edge chromatic number of a graph must be at least , the maximum vertex degree of the graph (Skiena 1990, p. 216). However, Vizing (1964) and Gupta (1966) showed that any graph can be edge-colored with at most  colors. There are therefore precisely two classes of graphs: those with edge chromatic number equal to  (class 1 graphs) and those with edge chromatic number equal to  (class 2 graphs).

By definition, the edge chromatic number of a graph  equals the (vertex) chromatic number of the line graph .

Computation of the edge chromatic number of a graph is implemented in the Wolfram Language as EdgeChromaticNumber[g]. Precomputed edge chromatic numbers for many named graphs can be obtained using GraphData[graph, "EdgeChromaticNumber"].

The edge chromatic number of a bipartite graph is , so all bipartite graphs are class 1 graphs.

Determining the edge chromatic number of a graph is an NP-complete problem (Holyer 1981; Skiena 1990, p. 216).

---

REFERENCES

Fiorini, S. and Wilson, R. Edge-Colourings of Graphs. Pittman, 1977.

Gupta, R. P. "The Chromatic Index and the Degree of a Graph." Not. Amer. Math. Soc. 13, 719, 1966.

Holyer, I. "The NP-Completeness of Edge Colorings." SIAM J. Comput. 10, 718-720, 1981.

Nemhauser, G. L. and Park, S. "A Polyhedral Approach to Edge Coloring." Operations Res. Lett. 10, 315-322, 1991.

Skiena, S. "Edge Colorings." §5.5.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 216, 1990.

Vizing, V. G. "On an Estimate of the Chromatic Class of a -Graph" [Russian]. Diskret. Analiz 3, 23-30, 1964.

اخر الاخبار

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

قسم الشؤون الطبية يقدم الخدمات الصحية والعلاجية لزائري مدينة سامراء

العتبة العباسية المقدسة تقدم خدماتها لزائري مرقد الإمامين العسكريين (عليهما السلام) في سامراء

المجمَع العلمي ووفد وزارة التربية يبحثان سبل التعاون المشترك

قسم الشؤون الفكرية يصدر العدد 192 من مجلة الرياحين للأطفال

المزيد

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

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

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

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

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

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