VertexChromaticNumber
gives the chromatic number for the vertices of the graph g.
Details and Options
- VertexChromaticNumber is also know as chromatic number.
- VertexChromaticNumber gives the smallest number of colors that can be assigned to the vertices of the graph g such that no two adjacent vertices have the same color.
Examples
open all close allBasic Examples (2)
Scope (6)
VertexChromaticNumber works with undirected graphs:
VertexChromaticNumber[[image]]VertexChromaticNumber[[image]]VertexChromaticNumber[[image]]VertexChromaticNumber[[image]]Use rules to specify the graph:
VertexChromaticNumber[{1 -> 2, 1 -> 3, 1 -> 4, 1 -> 5, 2 -> 3, 2 -> 5, 3 -> 4, 4 -> 5}]VertexChromaticNumber works with large graphs:
g = GridGraph[{10, 10, 10}];AbsoluteTiming[VertexChromaticNumber[g];]Applications (3)
Making schedules (1)
A university has a number of different subjects. Each student enrolled in some of these subjects. Build a graph where every vertex is a subject and an edge between two vertices means there is a common student:
g = [image];Schedule the minimum time slots such that no two exams with a common student are scheduled at same time:
VertexChromaticNumber[g]Mobile radio frequency assignment (1)
When frequencies are assigned to towers, frequencies assigned to all towers at the same location must be different. Build a graph where each vertex is a tower and an edge between two towers represents that they are in range of each other:
g = [image];Find the minimum number of frequencies needed:
VertexChromaticNumber[g]Map coloring (1)
Build a map where each vertex is an African country and an edge between two countries shows if they are adjacent:
g = [image];Color the map where any adjacent countries must be assigned a different color:
FindVertexColoring[g, ColorData[3, "ColorList"]];Annotate[g, {VertexSize -> 3, VertexStyle -> Thread[VertexList[g] -> %]}]Find the minimum number of colors:
VertexChromaticNumber[g]Properties & Relations (8)
The chromatic number for a cycle graph is 2 when it has an even number of vertices; otherwise, it is 3:
Table[VertexChromaticNumber[CycleGraph[n]], {n, 4, 7}]The chromatic number for a wheel graph is 4 when it has an even number of vertices; otherwise, it is 3:
Table[VertexChromaticNumber[WheelGraph[n]], {n, 4, 7}]Bipartite graphs are two-chromatic graphs:
graphs = {[image], [image]};VertexChromaticNumber[#] == 2& /@ graphsBipartiteGraphQ /@ graphsThe one-chromatic graphs are empty graphs:
graphs = {[image], [image], [image], [image], [image]};(VertexChromaticNumber[#] == 1)& /@ graphsEmptyGraphQ /@ graphsFor a graph with 
vertices and 
edges, its chromatic number 
is between 1 and 
:
g = RandomGraph[{5, 10}];χ = VertexChromaticNumber[g];1 <= χ <= VertexCount[g]
χ(χ - 1) <= 2EdgeCount[g]If a graph contains a clique of size 
, then its chromatic number is at least 
:
g = [image];VertexChromaticNumber[g] >= Length[First[FindClique[g]]]A graph with 
vertices, its chromatic number 
and independence number 
satisfy 
:
g = PetersenGraph[];χ = VertexChromaticNumber[g];α = Length[First[FindIndependentVertexSet[g]]];VertexCount[g] / α <= χUse FindVertexColoring to compute VertexChromaticNumber:
g = PetersenGraph[];Max[FindVertexColoring[g]]VertexChromaticNumber[g]Text
Wolfram Research (2021), VertexChromaticNumber, Wolfram Language function, https://reference.wolfram.com/language/ref/VertexChromaticNumber.html.
CMS
Wolfram Language. 2021. "VertexChromaticNumber." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/VertexChromaticNumber.html.
APA
Wolfram Language. (2021). VertexChromaticNumber. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/VertexChromaticNumber.html