FindVertexColoring

FindVertexColoring[g]

finds a coloring with minimal size for the vertices in the graph g.

FindVertexColoring[g,{c₁,c₂,…}]

finds a coloring {c₁,c₂,…,c_k} for the vertices in the graph g.

Details and Options

FindVertexColoring is also known as graph coloring and vertex labeling.
FindVertexColoring is typically used for modeling scheduling and assignment problems.

FindVertexColoring[g] gives a coloring {c₁,c₂,…,c_k} with minimal size for the vertices of g where c_i are integers and c_i is not equal to c_j for two adjacent vertices v_i and v_j of g with indices i and j.
FindVertexColoring[g,{c₁,c₂,…}] uses the specified colors c_i.
FindVertexColoring[g,l] is effectively equivalent to FindVertexColoring[g,{1,2,…,l}].

Examples

open allclose all

Basic Examples (2)

Find a vertex coloring of the Petersen graph:

Assign distinct colors to adjacent vertices of a graph:

Visualize the graph:

Scope (7)

FindVertexColoring works with undirected graphs:

Directed graphs:

Weighted graphs:

Multigraphs:

Use rules to specify the graph:

Assign distinct colors to adjacent vertices of a graph:

FindVertexColoring works with large graphs:

Applications (5)

Basic Applications (2)

Visualize vertex colorings of parametrized graphs:

Find a sequence of colors of CompleteGraph[n]:

CycleGraph[n]:

Making Schedule (1)

A university has a number of different subjects. Each student is 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:

Find a exam schedule such that no two exams with a common student are scheduled at same time:

Minimum time slots are needed to schedule all exams:

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:

Find the minimum number of frequencies needed:

Map Coloring (1)

Build a map where each vertex is an African country and there is an edge between two countries if they are adjacent:

Color the map with a minimum number of colors, where any adjacent countries must be assigned different colors:

Properties & Relations (6)

Bipartite graphs are two-colorable graphs:

The one-colorable graphs are empty graphs:

Use FindVertexColoring to compute VertexChromaticNumber:

An edge coloring of a graph is just a vertex coloring of its line graph:

A graph with vertices, its chromatic number and independence number satisfies ≤ :

A face coloring of a planar graph is a vertex coloring of its dual:

Top

FindVertexColoring

Details and Options

Examples

Basic Examples (2)

Scope (7)