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 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: 17-April-2024 ]}

BibLaTeX

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