WOLFRAM

Wolfram Language & System Documentation Center

EdgeChromaticNumber[g]

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

Details and Options
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Applications  
Tournament Schedule  
Properties & Relations  
See Also
Related Guides
History
Cite this Page

EdgeChromaticNumber

EdgeChromaticNumber[g]

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 all close all

Basic Examples  (2)

Find an edge chromatic number of the Petersen graph:

Wolfram Language code: EdgeChromaticNumber[PetersenGraph[]]

Edge chromatic numbers of the cycle graph:

Wolfram Language code: Table[EdgeChromaticNumber[CycleGraph[n]], {n, 2, 9}]

The formula:

Wolfram Language code: FindSequenceFunction[%, n - 1]

Scope  (6)

EdgeChromaticNumber works with undirected graphs:

Wolfram Language code: EdgeChromaticNumber[[image]]

Directed graphs:

Wolfram Language code: EdgeChromaticNumber[[image]]

Weighted graphs:

Wolfram Language code: EdgeChromaticNumber[[image]]

Multigraphs:

Wolfram Language code: EdgeChromaticNumber[[image]]

Use rules to specify the graph:

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

EdgeChromaticNumber works with large graphs:

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

Applications  (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 at least how many rounds need to be scheduled so that each pair of competitors plays each other in one of the rounds:

Wolfram Language code: EdgeChromaticNumber[g]

Find a schedule:

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

Color the games:

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];

Find the minimum number of weekends needed:

Wolfram Language code: EdgeChromaticNumber[g]

Assign games to the weekends on which they are played:

Wolfram Language code: FindEdgeColoring[g]

Properties & Relations  (5)

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

Wolfram Language code: Table[EdgeChromaticNumber[CycleGraph[n]], {n, 4, 7}]

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

Wolfram Language code: Table[EdgeChromaticNumber[WheelGraph[n]], {n, 4, 7}]

Using FindEdgeColoring to compute EdgeChromaticNumber:

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

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

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

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

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

Text

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

CMS

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

APA

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

BibTeX

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

BibLaTeX

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