Read More
Date: 9-2-2016
1409
Date: 6-8-2016
1419
Date: 9-3-2022
1286
|
A vertex coloring is an assignment of labels or colors to each vertex of a graph such that no edge connects two identically colored vertices. The most common type of vertex coloring seeks to minimize the number of colors for a given graph. Such a coloring is known as a minimum vertex coloring, and the minimum number of colors which with the vertices of a graph may be colored is called the chromatic number, denoted .
A minimum vertex coloring can be computed using MinimumVertexColoring[g] in the Wolfram Language package Combinatorica` . Brelaz's heuristic algorithm can be used to find a good, but not necessarily minimal, vertex coloring of a graph. It is implemented as BrelazColoring[g] in the Wolfram Language package Combinatorica` .
A vertex coloring of a graph with or fewer colors is known as a k-coloring. A graph having a -coloring (and therefore chromatic number ) is said to be a k-colorable graph, while a graph having chromatic number is called a k-chromatic graph. The only one-colorable (and therefore one-chromatic) graphs are empty graphs, and two-colorable graphs are exactly the bipartite graphs. The four-color theorem establishes that all planar graphs are 4-colorable.
Christofides, N. "An Algorithm for the Chromatic Number of a Graph." Computer J. 14, 38-39, 1971.
Gould, R. (Ed.). Graph Theory. Menlo Park, CA: Benjamin-Cummings, 1988.
Manvel, B. "Extremely Greedy Coloring Algorithms." In Graphs and Applications (Ed. F. Harary and J. Maybee). New York: Wiley, pp. 257-270, 1985.
Matula D. W.; Marble, G.; and Isaacson, J. D. "Graph Coloring Algorithms." In Graph Theory and Computing (Ed. R. Read). New York: Academic Press, pp. 109-122, 1972.S
kiena, S. "Finding a Vertex Coloring." §5.5.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 214-215, 1990.
Wilf, H. "Backtrack: An Expected Time Algorithm for the Graph Coloring Problem." Info. Proc. Let. 18, 119-121, 1984.
|
|
علامات بسيطة في جسدك قد تنذر بمرض "قاتل"
|
|
|
|
|
أول صور ثلاثية الأبعاد للغدة الزعترية البشرية
|
|
|
|
|
مدرسة دار العلم.. صرح علميّ متميز في كربلاء لنشر علوم أهل البيت (عليهم السلام)
|
|
|