# A Brief History of Edge-Colorings — with Personal Reminiscences

Bjarne Toft*, Robin J. Wilson

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

## Abstract

We begin with some basic remarks. If G is a graph, then its chromatic index or edge-chromatic number χ0(G) is the smallestnumber of colors needed to color its edges so that adjacent edges (those with a vertex in common) are colored differently; forexample, if G is an even cycle then χ0(G) = 2, and if G is an odd cycle then χ0(G) = 3. For complete graphs, χ0(Kn) = n−1 ifn is even and χ0(Kn) = n if n is odd, and for complete bipartite graphs, χ0(Kr,s) = max(r, s). We note that if the maximumvertex-degree in G is ∆, then χ0(G) ≥ ∆; for example, if G is the Petersen graph, which is regular of degree 3, then χ0(G) ≥ 3.However, it has no 3-edge-coloring, as Julius Petersen explained when he presented it in 1898 [32]. For, suppose that thereare just three colors, 1, 2, 3. Then any coloring of the outside pentagon must have the form 1, 2, 1, 2, 3 (for some permutationof the numbers, and taking account of symmetry). This forces the colors on the spokes, as shown in Figure 1. But then thetwo bold edg
Original language English Discrete Mathematics Letters 6 38-46 2664-2557 https://doi.org/10.47443/dml.2021.s105 Published - 2021

### Bibliographical note

Special Volume on the Occasion of the 100th Anniversary of Frank Harary’s Birth

## Keywords

• Edge-coloring
• Frank Harary
• Graph theory history