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

Bjarne Toft*, Robin J. Wilson

*Kontaktforfatter

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

## Abstrakt

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
Originalsprog Engelsk Discrete Mathematics Letters 6 38-46 2664-2557 https://doi.org/10.47443/dml.2021.s105 Udgivet - 2021

### Bibliografisk note

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

## Fingeraftryk

Dyk ned i forskningsemnerne om 'A Brief History of Edge-Colorings — with Personal Reminiscences'. Sammen danner de et unikt fingeraftryk.