Graph Edge Coloring: A Survey

Yan Cao, Guantao Chen, Guangming Jing*, Michael Stiebitz, Bjarne Toft

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

Graph edge coloring has a rich theory, many applications and beautiful conjectures, and it is studied not only by mathematicians, but also by computer scientists. In this survey, written for the non-expert, we shall describe some main results and techniques and state some of the many popular conjectures in the theory. Besides known results a new basic result about brooms is obtained.

Original languageEnglish
JournalGraphs and Combinatorics
Volume35
Issue number1
Pages (from-to)33-66
ISSN0911-0119
DOIs
Publication statusPublished - Jan 2019

    Fingerprint

Keywords

  • Adjacency lemma
  • Chromatic index
  • Edge coloring

Cite this