Read More
Date: 6-5-2022
1395
Date: 6-5-2022
2099
Date: 26-4-2022
1533
|
The chromatic number of a graph is the smallest number of colors needed to color the vertices of so that no two adjacent vertices share the same color (Skiena 1990, p. 210), i.e., the smallest value of possible to obtain a k-coloring. Minimal colorings and chromatic numbers for a sample of graphs are illustrated above.
The chromatic number of a graph is most commonly denoted (e.g., Skiena 1990, West 2000, Godsil and Royle 2001, Pemmaraju and Skiena 2003), but occasionally also .
Empty graphs have chromatic number 1, while non-empty bipartite graphs have chromatic number 2.
The chromatic number of a graph is also the smallest positive integer such that the chromatic polynomial . Calculating the chromatic number of a graph is an NP-complete problem (Skiena 1990, pp. 211-212). Or, in the words of Harary (1994, p. 127), "no convenient method is known for determining the chromatic number of an arbitrary graph." However, Mehrotra and Trick (1996) devised a column generation algorithm for computing chromatic numbers and vertex colorings which solves most small to moderate-sized graph quickly.
Computation of the chromatic number of a graph is implemented in the Wolfram Language as VertexChromaticNumber[g]. Precomputed chromatic numbers for many named graphs can be obtained using GraphData[graph, "ChromaticNumber"].
The chromatic number of a graph must be greater than or equal to its clique number. A graph is called a perfect graph if, for each of its induced subgraphs , the chromatic number of equals the largest number of pairwise adjacent vertices in . A graph for which the clique number is equal to the chromatic number (with no further restrictions on induced subgraphs) is said to be weakly perfect.
By definition, the edge chromatic number of a graph equals the chromatic number of the line graph .
Brooks' theorem states that the chromatic number of a graph is at most the maximum vertex degree , unless the graph is complete or an odd cycle, in which case colors are required.
A graph with chromatic number is said to be bicolorable, and a graph with chromatic number is said to be three-colorable. In general, a graph with chromatic number is said to be an k-chromatic graph, and a graph with chromatic number is said to be k-colorable.
The following table gives the chromatic numbers for some named classes of graphs.
graph | |
complete graph | |
cycle graph , | |
star graph , | 2 |
wheel graph , |
For any two positive integers and , there exists a graph of girth at least and chromatic number at least (Erdős 1961; Lovász 1968; Skiena 1990, p. 215).
The chromatic number of a surface of genus is given by the Heawood conjecture,
where is the floor function. is sometimes also denoted (which is unfortunate, since commonly refers to the Euler characteristic). For , 1, ..., the first few values of are 4, 7, 8, 9, 10, 11, 12, 12, 13, 13, 14, 15, 15, 16, ... (OEIS A000934).
Erdős (1959) proved that there are graphs with arbitrarily large girth and chromatic number (Bollobás and West 2000).
Bollobás, B. and West, D. B. "A Note on Generalized Chromatic Number and Generalized Girth." Discr. Math. 213, 29-34, 2000.
Chartrand, G. "A Scheduling Problem: An Introduction to Chromatic Numbers." §9.2 in Introductory Graph Theory. New York: Dover, pp. 202-209, 1985.
Eppstein, D. "The Chromatic Number of the Plane." http://www.ics.uci.edu/~eppstein/junkyard/plane-color.html.Erdős, P. "Graph Theory and Probability." Canad. J. Math. 11, 34-38, 1959.
Erdős, P. "Graph Theory and Probability II." Canad. J. Math. 13, 346-352, 1961.
Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, p. 9, 1984.
Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, 2001.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.
Lovász, L. "On Chromatic Number of Finite Set-Systems." Acta Math. Acad. Sci. Hungar. 19, 59-67, 1968.
Mehrotra, A. and Trick, M. A. "A Column Generation Approach for Graph Coloring." INFORMS J. on Computing 8, 344-354, 1996.
https://mat.tepper.cmu.edu/trick/color.pdf.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, 2003.
Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.
Sloane, N. J. A. Sequences A000012/M0003, A000934/M3292, A068917, A068918, and A068919 in "The On-Line Encyclopedia of Integer Sequences."Trick, West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.
|
|
تفوقت في الاختبار على الجميع.. فاكهة "خارقة" في عالم التغذية
|
|
|
|
|
أمين عام أوبك: النفط الخام والغاز الطبيعي "هبة من الله"
|
|
|
|
|
قسم شؤون المعارف ينظم دورة عن آليات عمل الفهارس الفنية للموسوعات والكتب لملاكاته
|
|
|