A brief history of edge-colorings – with personal reminiscences

2021/03/11 by Bjarne Toft, Robin Wilson · 1 citation
Computer Science · #Advanced Graph Theory Research #Enhanced Data Rates for GSM Evolution #Computer science #Astrobiology #Art #Artificial intelligence #Biology

paper · pdf · doi:10.47443/dml.2021.s105

openalex publication_date 2021/03/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/16

Abstract

In this article we survey some important milestones in the history of edge-colorings of graphs, from the earliest contributions of Peter Guthrie Tait and Dénes König to very recent work

Citations

• The List Chromatic Index of a Bipartite Multigraph
• Planar Graphs of Maximum Degree Seven are Class I
• The NP-Completeness of Edge-Coloring
• On the chromatic index of almost all graphs
• A Theorem on Coloring the Lines of a Network
• On the Geographical Problem of the Four Colours

Cited by

• Vizing's theorem [wikipedia]

Related

• On Vizing's edge colouring question
• It was not known about simple cycles
• Fast and Simple Edge-Coloring Algorithms
• Tools for parsimonious edge-colouring of graphs with maximum degree three
• Graph Colouring: A Visual Tour