A Brief History of Edge-Colorings — with Personal Reminiscences

Bjarne Toft*, Robin J. Wilson


Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

26 Downloads (Pure)


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
TidsskriftDiscrete Mathematics Letters
Sider (fra-til)38-46
StatusUdgivet - 2021

Bibliografisk note

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


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