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

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_2024_edgechromaticnumber, author="Wolfram Research", title="{EdgeChromaticNumber}", year="2021", howpublished="\url{https://reference.wolfram.com/language/ref/EdgeChromaticNumber.html}", note=[Accessed: 21-December-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_edgechromaticnumber, organization={Wolfram Research}, title={EdgeChromaticNumber}, year={2021}, url={https://reference.wolfram.com/language/ref/EdgeChromaticNumber.html}, note=[Accessed: 21-December-2024 ]}