# 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 allclose all

## Basic Examples(2)

Find a vertex chromatic number of the Petersen graph:

Chromatic numbers of the complete graph:

The formula:

## Scope(6)

VertexChromaticNumber works with undirected graphs:

Directed graphs:

Weighted graphs:

Multigraphs:

Use rules to specify the graph:

VertexChromaticNumber works with large graphs:

## 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:

Schedule the minimum time slots such that no two exams with a common student are scheduled at same time:

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 an edge between two countries shows if they are adjacent:

Color the map where any adjacent countries must be assigned a different color:

Find the minimum number of colors:

## Properties & Relations(8)

The chromatic number for a cycle graph is 2 when it has an even number of vertices; otherwise, it is 3:

The chromatic number for a wheel graph is 4 when it has an even number of vertices; otherwise, it is 3:

Bipartite graphs are two-chromatic graphs:

The one-chromatic graphs are empty graphs:

For a graph with vertices and edges, its chromatic number is between 1 and : :

If a graph contains a clique of size , then its chromatic number is at least :

A graph with vertices, its chromatic number and independence number satisfy :

Use FindVertexColoring to compute VertexChromaticNumber: