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

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

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_2023_findedgecoloring, author="Wolfram Research", title="{FindEdgeColoring}", year="2021", howpublished="\url{https://reference.wolfram.com/language/ref/FindEdgeColoring.html}", note=[Accessed: 30-September-2023 ]}

BibLaTeX

@online{reference.wolfram_2023_findedgecoloring, organization={Wolfram Research}, title={FindEdgeColoring}, year={2021}, url={https://reference.wolfram.com/language/ref/FindEdgeColoring.html}, note=[Accessed: 30-September-2023 ]}