تلوين مخطط

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

تلوين رؤوس مناسب في مخطط پيترسن بثلاث ألوان، وهو أقل عدد ممكن.

مسألة NP كاملة
قابلية الإرضاء 3SAT NAE OIT
تلوين مخطط تلوين مخطط بثلاثة ألوان تلوين مخطط مستو بثلاثة ألوان
زمرة كبرى
مسار هاملتونياني
عدل

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 التعريف والمصطلحات

This graph can be 3-colored in 12 different ways.

 متعددة الحدود اللونية

All nonisomorphic graphs on 3 vertices and their chromatic polynomials. The empty graph E₃ (red) admits a 1-coloring, the others admit no such colorings. The green graph admits 12 colorings with 3 colors.

المقالة الرئيسية: Chromatic polynomial

الألوان المتاحة	1	2	3	4	…
عدد التلوينات	0	0	12	72	…

The chromatic polynomial is a function P(G, t) that counts the number of t-colorings of G. As the name indicates, for a given G the function is indeed a polynomial in t. For the example graph, P(G, t) = t(t − 1)²(t − 2), and indeed P(G, 4) = 72.

The chromatic polynomial includes at least as much information about the colorability of G as does the chromatic number. Indeed, χ is the smallest positive integer that is not a root of the chromatic polynomial

$\chi (G)=\min\{k\colon P(G,k)>0\}.$

متعددات الحدود اللونية لمخططات محددة

Triangle K3	$t(t-1)(t-2)$
Complete graph Kn	$t(t-1)(t-2)\cdots (t-(n-1))$
Tree with n vertices	$t(t-1)^{n-1}$
Cycle Cn	$(t-1)^{n}+(-1)^{n}(t-1)$
Petersen graph	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$

 تلوين الأضلاع

المقالة الرئيسية: تلوين الأضلاع

 خصائص

تحديد أقل عدد ممكن من الألوان يسمى عدد التلوين. و تحديد هذا العدد من المشاكل الكاملة, و هذا المشكل له علاقة قريبة جدا من مشكلة المخطط الكامل ضمن مخطط و مشكلة المخطط المستقر ضمن مخطط.

 الخوارزميات

تلوين المخطط
القرار
الاسم	Graph coloring, vertex coloring, k-coloring
المُدخل	Graph G with n vertices. Integer k
المُخرج	هل G تتيح تلوين رؤوس صحيح بعدد k من الألوان؟
زمن الحساب	O(2 nn)
التعقد	NP-complete
اختزال من	3-Satisfiability
Garey–Johnson	GT4
Optimisation
الاسم	الرقم اللوني
المُدخل	المخطط G ذو n من الرؤوس.
المُخرج	χ(G)
التعقد	NP-hard
امكانية التقريب	O(n (log n)−3(log log n)2)
عدم امكانية التقريب	O(n1−ε) إلا إذا P = NP
مشكلة العـد
الاسم	متعددة الحدود اللونية
المُدخل	المخطط G حيث n رؤوس. عدد صحيح k
المُخرج	العدد P (G,k) لعدد k مناسب -تلوينات G
زمن الحساب	O(2 nn)
التعقد	#P-complete
امكانية التقريب	FPRAS لحالات محددة
عدم امكانية التقريب	No PTAS إلا إذا P = NP

 تلوين طماع

المقالة الرئيسية: تلوين طماع

Two greedy colorings of the same graph using different vertex orders. The right example generalises to 2-colorable graphs with n vertices, where the greedy algorithm expends $n/2$ colors.

 التلوين بثلاثة ألوان

تلوين مخطط ما باستعمال ثلاثة ألوان فقط، هو أيضا مشكل كامل حيث يمكن اختصار أي مشكل من صنف المشاكل غير المحددة لمشكل التلوين بثلاثة ألوان.

 التطبيقات

 تلوينات أخرى

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 نظرية رامسي

المقالة الرئيسية: نظرية رامسي

 تلوينات أخرى

List coloring

Each vertex chooses from a list of colors

List edge-coloring

Each edge chooses from a list of colors

Total coloring

Vertices and edges are colored

Harmonious coloring

Every pair of colors appears on at most one edge

Complete coloring

Every pair of colors appears on at least one edge

Exact coloring

Every pair of colors appears on exactly one edge

Acyclic coloring

Every 2-chromatic subgraph is acyclic

Star coloring

Every 2-chromatic subgraph is a disjoint collection of stars

Strong coloring

Every color appears in every partition of equal size exactly once

Strong edge coloring

Edges are colored such that each color class induces a matching (equivalent to coloring the square of the line graph)

Equitable coloring

The sizes of color classes differ by at most one

T-coloring

Distance between two colors of adjacent vertices must not belong to fixed set T

Rank coloring

If two vertices have the same color i, then every path between them contain a vertex with color greater than i

Interval edge-coloring

A color of edges meeting in a common vertex must be contiguous

Circular coloring

Motivated by task systems in which production proceeds in a cyclic way

Path coloring

Models a routing problem in graphs

Fractional coloring

Vertices may have multiple colors, and on each edge the sum of the color parts of each vertex is not greater than one

Oriented coloring

Takes into account orientation of edges of the graph

Cocoloring

An improper vertex coloring where every color class induces an independent set or a clique

Subcoloring

An improper vertex coloring where every color class induces a union of cliques

Weak coloring

An improper vertex coloring where every non-isolated node has at least one neighbor with a different color

Sum-coloring

The criterion of minimalization is the sum of colors

Coloring can also be considered for signed graphs and gain graphs.

 انظر أيضاً

• Circular coloring
• Critical graph
• Cycle rank - Ordered chromatic number
• Graph homomorphism
• Mathematics of Sudoku
• Uniquely colorable graph

 وصلات خارجية

• Graph Coloring Page by Joseph Culberson (graph coloring programs)
• CoLoRaTiOn by Jim Andrews and Mike Fellows is a graph coloring puzzle
• GF-Graph Coloring Program [1]
• Links to Graph Coloring source codes
• Code for efficiently computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle