Edge Chromatic Number
المؤلف:
Fiorini, S. and Wilson, R.
المصدر:
Edge-Colourings of Graphs. Pittman, 1977.
الجزء والصفحة:
...
26-3-2022
1599
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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
