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

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

Wolfram Research (2021), VertexChromaticNumber, Wolfram Language function, https://reference.wolfram.com/language/ref/VertexChromaticNumber.html.

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

#### BibTeX

@misc{reference.wolfram_2023_vertexchromaticnumber, author="Wolfram Research", title="{VertexChromaticNumber}", year="2021", howpublished="\url{https://reference.wolfram.com/language/ref/VertexChromaticNumber.html}", note=[Accessed: 28-September-2023 ]}

#### BibLaTeX

@online{reference.wolfram_2023_vertexchromaticnumber, organization={Wolfram Research}, title={VertexChromaticNumber}, year={2021}, url={https://reference.wolfram.com/language/ref/VertexChromaticNumber.html}, note=[Accessed: 28-September-2023 ]}