k-Coloring

 

A -coloring of a graph  is a vertex coloring that is an assignment of one of  possible colors to each vertex of  (i.e., a vertex coloring) such that no two adjacent vertices receive the same color.

Note that a -coloring may contain fewer than  colors for .

A -coloring of a graph can be computed using MinimumVertexColoring[g, k] in the Wolfram Language package Combinatorica` , and all -colorings may be computed using MinimumVertexColoring[g, k, All] (where, however, the command returns colorings that differ by permutation of colors only a single time).

The number of distinct -colorings (where permutations of colors are counted separately) of a graph  is given by , where  is the chromatic polynomial of .

---

REFERENCES

Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 13, 1986.

اخر الاخبار

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

بذكرى شهادته.. جموع الزائرين تشيع النعش الرمزي للإمام الكاظم (عليه السلام) عند مرقده الطاهر في بغداد

العتبة العباسية المقدسة تنظم مجلس عزاء بذكرى شهادة الإمام الكاظم (عليه السلام)

جموع المؤمنين تشيّع النعش الرمزي للإمام الكاظم (عليه السلام) عند العتبتين المقدستين

شعبة التوجيه الديني النسوي تنظم مسابقة ميدانية بذكرى شهادة الإمام الكاظم (عليه السلام)

المزيد

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

الخبز الأسمر أم الأبيض.. أيهما أفضل لضبط سكر الدم؟

عقاقير التخسيس و"الانتحار".. الحكومة الأميركية تحسم الجدل

الهرم الغذائي الجديد.. لماذا يعد "انقلابا" في خارطة الطعام؟

لحماية ظهرك وقلبك في آن واحد.. ما وضعية النوم الصحيحة؟

المزيد

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

كيف يعزز الضوء الطبيعي تفكيرك وانتباهك خلال اليوم

سابقة.. طاقم من محطة الفضاء الدولية يعود إلى الأرض مبكرا

منصات التواصل تضرّ بنفسية المراهقين… والفتيات الأكثر تأثرا

ابتكار ألماني قد يغيّر مستقبل صناعة البلاستيك

المزيد

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

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