Vertex Coloring

 

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.

---

REFERENCES

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.

اخر الاخبار

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

مؤتمر السيد المجاهد يشهد عرض فيلم وثائقي عن سيرته العلمية ومشروع إحياء تراثه

بحث حوزوي يتناول التمييز بين المعجزة والسحر عند السيد المجاهد

بحث يناقش أثر القواعد العقلية في استنباط الأحكام الشرعية عند السيد محمد المجاهد

بحث علمي يناقش ردود السيد المجاهد على اللغويين والنحويين في كتابه (مفاتيح الأصول)

المزيد

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

هل توقيت نشاطك اليومي يؤثر على صحة دماغك؟.. العلماء يجيبون

"مشروب محبوب" يخفي فوائد لا يعرفها كثيرون

طبيب يكشف 5 أنواع للسعال.. بعضها خطير

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

المزيد

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

دراسة: تغيّرات في أسلوب القيادة قد تكشف مبكرا عن الخرف !

عمرها 773 ألف سنة.. اكتشاف أقدم أحافير بشرية في المغرب

"اختراق علمي".. اختبار دم في منزلك قد يكشف ألزهايمر

ماذا يحدث للجسم عند قطع الكافيين فجأة؟

المزيد

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

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