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

3 Downloads (Pure)

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 languageEnglish
JournalDiscrete Mathematics Letters
Volume6
Pages (from-to)38-46
ISSN2664-2557
DOIs
Publication statusPublished - 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

Fingerprint Dive into the research topics of 'A Brief History of Edge-Colorings — with Personal Reminiscences'. Together they form a unique fingerprint.

Cite this