TY - JOUR

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

AU - Toft, Bjarne

AU - Wilson, Robin J.

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

PY - 2021

Y1 - 2021

N2 - 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

AB - 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

KW - Edge-coloring

KW - Frank Harary

KW - Graph theory history

U2 - 10.47443/dml.2021.s105

DO - 10.47443/dml.2021.s105

M3 - Journal article

SN - 2664-2557

VL - 6

SP - 38

EP - 46

JO - Discrete Mathematics Letters

JF - Discrete Mathematics Letters

ER -