# FindEdgeColoring

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

FindEdgeColoring[g,{c1,c2,}]

finds a coloring {c1,c2,,ck} for the edges in the graph g.

# Details • FindEdgeColoring is also known as graph coloring and edge labeling.
• FindEdgeColoring is typically used for modeling scheduling and assignment problems.
• • finds a coloring {c1,c2,,ck} with minimal size for the edges of g where ci are integers and ci is not equal to cj for two adjacent edges ei and ej of g with indices i and j.
• FindEdgeColoring[g,{c1,c2,}] uses the specified colors ci.
• FindEdgeColoring[g,l] is effectively equivalent to FindEdgeColoring[g,{1,2,,l}].

# Examples

open allclose all

## Basic Examples(2)

Find an edge coloring of the Petersen graph:

Assign distinct colors to adjacent edges of a graph:

Visualize the graph:

## Scope(7)

FindEdgeColoring works with undirected graphs:

Directed graphs:

Weighted graphs:

Multigraphs:

Use rules to specify the graph:

Assign distinct colors to adjacent edges of a graph:

FindVertexColoring works with large graphs:

## Applications(3)

### Basic Applications(1)

Visualize edge colorings of parametrized graphs:

### 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 a schedule with as few rounds as possible so that each pair of competitors plays each other in one of the rounds:

Find the pairs of competitors who will play the first round:

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:

Assign games to the weekends on which they are played:

Find the minimum number of weekends needed:

## Properties & Relations(4)

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

Using FindEdgeColoring to compute EdgeChromaticNumber:

The number of colors needed to edge color a simple graph is either its maximum degree or :

The number of colors needed to edge color a bipartite graph is its maximum degree: