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 -