المرجع الالكتروني للمعلوماتية
المرجع الألكتروني للمعلوماتية

الرياضيات
عدد المواضيع في هذا القسم 9761 موضوعاً
تاريخ الرياضيات
الرياضيات المتقطعة
الجبر
الهندسة
المعادلات التفاضلية و التكاملية
التحليل
علماء الرياضيات

Untitled Document
أبحث عن شيء أخر

الترادف
19-7-2016
انفصال القمر
2023-05-30
نضج ثمار الكاكي وقطافها
3-1-2016
المواسعة الموزعة للملف distributed capacitance of a coil
7-9-2018
أضواء على دعاء اليوم الثاني والعشرين.
2024-05-02
الطريقة العامة لتحضير مشتقات الثايويوريا (T33-T1)
2024-07-14

Chromatic Number  
  
2549   04:24 مساءً   date: 24-3-2022
Author : Bollobás, B. and West, D. B
Book or Source : "A Note on Generalized Chromatic Number and Generalized Girth." Discr. Math. 213
Page and Part : ...


Read More
Date: 24-2-2022 1286
Date: 20-4-2022 1422
Date: 12-4-2022 1547

Chromatic Number

 

ChromaticNumber

The chromatic number of a graph G is the smallest number of colors needed to color the vertices of G so that no two adjacent vertices share the same color (Skiena 1990, p. 210), i.e., the smallest value of k 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 G is most commonly denoted chi(G) (e.g., Skiena 1990, West 2000, Godsil and Royle 2001, Pemmaraju and Skiena 2003), but occasionally also gamma(G).

Empty graphs have chromatic number 1, while non-empty bipartite graphs have chromatic number 2.

The chromatic number of a graph G is also the smallest positive integer z such that the chromatic polynomial pi_G(z)>0. 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 g_i, the chromatic number of g_i equals the largest number of pairwise adjacent vertices in g_i. 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 G equals the chromatic number of the line graph L(G).

Brooks' theorem states that the chromatic number of a graph is at most the maximum vertex degree Delta, unless the graph is complete or an odd cycle, in which case Delta+1 colors are required.

A graph with chromatic number <=2 is said to be bicolorable, and a graph with chromatic number <=3 is said to be three-colorable. In general, a graph with chromatic number k is said to be an k-chromatic graph, and a graph with chromatic number <=k is said to be k-colorable.

The following table gives the chromatic numbers for some named classes of graphs.

graph G gamma(G)
complete graph K_n n
cycle graph C_nn>1 {3   for n odd; 2   for n even
star graph S_nn>1 2
wheel graph W_nn>2 {3   for n odd; 4   for n even

For any two positive integers g and k, there exists a graph of girth at least g and chromatic number at least k (Erdős 1961; Lovász 1968; Skiena 1990, p. 215).

The chromatic number of a surface of genus g is given by the Heawood conjecture,

 gamma(g)=|_1/2(7+sqrt(48g+1))_|,

where |_x_| is the floor function. gamma(g) is sometimes also denoted chi(g) (which is unfortunate, since chi(g)=2-2g commonly refers to the Euler characteristic). For g=0, 1, ..., the first few values of chi(g) 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).


REFERENCES

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.




الجبر أحد الفروع الرئيسية في الرياضيات، حيث إن التمكن من الرياضيات يعتمد على الفهم السليم للجبر. ويستخدم المهندسون والعلماء الجبر يومياً، وتعول المشاريع التجارية والصناعية على الجبر لحل الكثير من المعضلات التي تتعرض لها. ونظراً لأهمية الجبر في الحياة العصرية فإنه يدرّس في المدارس والجامعات في جميع أنحاء العالم. ويُعجب الكثير من الدارسين للجبر بقدرته وفائدته الكبيرتين، إذ باستخدام الجبر يمكن للمرء أن يحل كثيرًا من المسائل التي يتعذر حلها باستخدام الحساب فقط.وجاء اسمه من كتاب عالم الرياضيات والفلك والرحالة محمد بن موسى الخورازمي.


يعتبر علم المثلثات Trigonometry علماً عربياً ، فرياضيو العرب فضلوا علم المثلثات عن علم الفلك كأنهما علمين متداخلين ، ونظموه تنظيماً فيه لكثير من الدقة ، وقد كان اليونان يستعملون وتر CORDE ضعف القوسي قياس الزوايا ، فاستعاض رياضيو العرب عن الوتر بالجيب SINUS فأنت هذه الاستعاضة إلى تسهيل كثير من الاعمال الرياضية.

تعتبر المعادلات التفاضلية خير وسيلة لوصف معظم المـسائل الهندسـية والرياضـية والعلمية على حد سواء، إذ يتضح ذلك جليا في وصف عمليات انتقال الحرارة، جريان الموائـع، الحركة الموجية، الدوائر الإلكترونية فضلاً عن استخدامها في مسائل الهياكل الإنشائية والوصف الرياضي للتفاعلات الكيميائية.
ففي في الرياضيات, يطلق اسم المعادلات التفاضلية على المعادلات التي تحوي مشتقات و تفاضلات لبعض الدوال الرياضية و تظهر فيها بشكل متغيرات المعادلة . و يكون الهدف من حل هذه المعادلات هو إيجاد هذه الدوال الرياضية التي تحقق مشتقات هذه المعادلات.