# EdgeChromaticNumber

gives the chromatic number for the edges of the graph g.

# Details and Options • EdgeChromaticNumber is also known as chromatic index.
• • EdgeChromaticNumber gives the smallest number of colors that can be assigned to the edges of the graph g such that no two adjacent edges have the same color.

# Examples

open allclose all

## Basic Examples(2)

Find an edge chromatic number of the Petersen graph:

Edge chromatic numbers of the cycle graph:

The formula:

## Scope(6)

EdgeChromaticNumber works with undirected graphs:

Directed graphs:

Weighted graphs:

Multigraphs:

Use rules to specify the graph:

EdgeChromaticNumber works with large graphs:

## Applications(2)

### Tounament Schedule(2)

To schedule a round-robin tournament, build a graph where vertices correspond to the competitors in the tournament and the edges correspond to games:

Find at least how many rounds need to be scheduled so that each pair of competitors plays each other in one of the rounds:

Find a schedule:

Color the games:

In the National Football League, the pairs of teams that will play each other in a given year are determined based on the teams' records from the previous year. Build a graph where vertices correspond to the teams and the edges correspond to games:

Find the minimum number of weekends needed:

Assign games to the weekends on which they are played:

## Properties & Relations(5)

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

The chromatic index for a wheel graph is one less than the number of vertices:

Using FindEdgeColoring to compute EdgeChromaticNumber:

The chromatic index for a simple graph is either its maximum degree or :

The chromatic index for a bipartite graph is its maximum degree: