WOLFRAM

Wolfram Language & System Documentation Center

FindEdgeColoring[g]

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 and Options
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Applications  
Basic Applications  
Tournament Schedule  
Properties & Relations  
See Also
Related Guides
History
Cite this Page

FindEdgeColoring

FindEdgeColoring[g]

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 and Options

  • FindEdgeColoring is also known as graph coloring and edge labeling.
  • FindEdgeColoring is typically used for modeling scheduling and assignment problems.
  • FindEdgeColoring[g] 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 all close all

Basic Examples  (2)

Find an edge coloring of the Petersen graph:

Wolfram Language code: FindEdgeColoring[PetersenGraph[]]

Assign distinct colors to adjacent edges of a graph:

Wolfram Language code: g = PetersenGraph[];
Wolfram Language code: FindEdgeColoring[g, ColorData[106, "ColorList"]]

Visualize the graph:

Wolfram Language code: Annotate[g, {EdgeStyle -> Thread[EdgeList[g] -> %]}]

Scope  (7)

FindEdgeColoring works with undirected graphs:

Wolfram Language code: FindEdgeColoring[[image]]

Directed graphs:

Wolfram Language code: FindEdgeColoring[[image]]

Weighted graphs:

Wolfram Language code: FindEdgeColoring[[image]]

Multigraphs:

Wolfram Language code: FindEdgeColoring[[image]]

Use rules to specify the graph:

Wolfram Language code: FindEdgeColoring[{1 -> 2, 1 -> 3, 1 -> 4, 1 -> 5, 2 -> 3, 2 -> 5, 3 -> 4, 4 -> 5}]

Assign distinct colors to adjacent edges of a graph:

Wolfram Language code: FindEdgeColoring[[image], ColorData[3, "ColorList"]]

FindVertexColoring works with large graphs:

Wolfram Language code: g = GridGraph[{10, 10, 10}];
Wolfram Language code: AbsoluteTiming[FindEdgeColoring[g];]

Applications  (3)

Basic Applications  (1)

Visualize edge colorings of parametrized graphs:

Wolfram Language code: coloring[g_] := Annotate[g, {...}]
Wolfram Language code: Multicolumn[Table[coloring[g], {g, {...}}], 3, Spacings -> 2]

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

Wolfram Language code: g = [image];

Find a schedule with as few rounds as possible so that each pair of competitors plays each other in one of the rounds:

Wolfram Language code: res = FindEdgeColoring[g]

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

Wolfram Language code: EdgeList[g][[Flatten@Position[res, 1]]]

Color the games:

Wolfram Language code: FindEdgeColoring[g, ColorData[106, "ColorList"]];
Wolfram Language code: Annotate[g, {EdgeStyle -> Thread[EdgeList[g] -> Thread[{Thickness[0.02], %}]]}]

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:

Wolfram Language code: g = [image];

Assign games to the weekends on which they are played:

Wolfram Language code: FindEdgeColoring[g]

Find the minimum number of weekends needed:

Wolfram Language code: Max[%]

Properties & Relations  (4)

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

Wolfram Language code: g = PetersenGraph[]
Wolfram Language code: FindVertexColoring[LineGraph[g]]
Wolfram Language code: FindEdgeColoring[g]

Using FindEdgeColoring to compute EdgeChromaticNumber:

Wolfram Language code: g = PetersenGraph[];
Wolfram Language code: Max[FindEdgeColoring[g]]
Wolfram Language code: EdgeChromaticNumber[g]

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

Wolfram Language code: g = Table[RandomGraph[{5, i}], {i, 10}];
Wolfram Language code: Max[FindEdgeColoring[#]]& /@ g
Wolfram Language code: Max[VertexDegree[#]]& /@ g

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

Wolfram Language code: g = {[image], [image], [image], [image]};
Wolfram Language code: BipartiteGraphQ /@ g
Wolfram Language code: Max[FindEdgeColoring[#]]& /@ g
Wolfram Language code: Max[VertexDegree[#]]& /@ g
Wolfram Research (2021), FindEdgeColoring, Wolfram Language function, https://reference.wolfram.com/language/ref/FindEdgeColoring.html.

Text

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

CMS

Wolfram Language. 2021. "FindEdgeColoring." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/FindEdgeColoring.html.

APA

Wolfram Language. (2021). FindEdgeColoring. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindEdgeColoring.html

BibTeX

@misc{reference.wolfram_2026_findedgecoloring, author="Wolfram Research", title="{FindEdgeColoring}", year="2021", howpublished="\url{https://reference.wolfram.com/language/ref/FindEdgeColoring.html}", note=[Accessed: 13-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_findedgecoloring, organization={Wolfram Research}, title={FindEdgeColoring}, year={2021}, url={https://reference.wolfram.com/language/ref/FindEdgeColoring.html}, note=[Accessed: 13-June-2026]}