# FindVertexColoring

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

FindVertexColoring[g,{c1,c2,}]

finds a coloring {c1,c2,,ck} 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.
• • gives a coloring {c1,c2,,ck} with minimal size for the vertices of g where ci are integers and ci is not equal to cj for two adjacent vertices vi and vj of g with indices i and j.
• FindVertexColoring[g,{c1,c2,}] uses the specified colors ci.
• 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 :

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:

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: