TOPICS
Search

Strong Edge Coloring


A strong edge coloring is an edge coloring of a simple graph in which every color class is an induced matching. Thus edges of the same color neither share a graph vertex nor have endpoints joined by another graph edge (Faudree et al. 1990).

The strong chromatic index is the least number of colors in such a coloring. It equals the chromatic number of the graph square of the line graph. The Erdős-Nešetril conjecture predicts an upper bound of 5Delta^2/4, where Delta is the maximum vertex degree.

The Brualdi-Quinn conjecture bounds the strong chromatic index of a bipartite graph by Delta_ADelta_B, where Delta_A and Delta_B are the maximum vertex degrees on the two sides (Brualdi and Quinn Massey 1993). Luo et al. (2026) proved this bound for the fractional chromatic number of the graph square of the line graph. Equality is attained by complete bipartite graphs. For Delta=max(Delta_A,Delta_B)>=1, the ordinary strong chromatic index is at most (1+12sqrt(lnDelta)/Delta^(1/4))Delta_ADelta_B. The conjectured exact bound remains open.


See also

Edge Coloring, Erdős-Nešetril Conjecture, Induced Matching

Explore with Wolfram|Alpha

References

Brualdi, R. A. and Quinn Massey, J. J. "Incidence and Strong Edge Colorings of Graphs." Disc. Math. 122, 51-58, 1993.Faudree, R. J.; Schelp, R. H.; Gyárfás, A.; and Tuza, Zs. "The Strong Chromatic Index of Graphs." Ars Combin. 29B, 205-211, 1990.Luo, R.; Yu, G.; and Zhou, X. "The Brualdi-Quinn Conjecture on Strong Edge-Coloring Holds Fractionally and Asymptotically." 7 Nov 2026. https://arxiv.org/abs/2611.10883v1.

Cite this as:

Weisstein, Eric W. "Strong Edge Coloring." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/StrongEdgeColoring.html

Subject classifications