Graph Edge Coloring: A Survey

Yan Cao; Guantao Chen; Guangming Jing; Michael Stiebitz; Bjarne Toft

doi:10.1007/s00373-018-1986-5

Graph Edge Coloring: A Survey

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

Research output: Contribution to journal › Article › peer-review

20 Scopus citations

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 language	English (US)
Pages (from-to)	33-66
Number of pages	34
Journal	Graphs and Combinatorics
Volume	35
Issue number	1
DOIs	https://doi.org/10.1007/s00373-018-1986-5
State	Published - Jan 2 2019
Externally published	Yes

Keywords

Adjacency lemma
Chromatic index
Edge coloring

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00373-018-1986-5

Cite this

@article{a334b0daa9f24fd69b899cc41f2f34d2,

title = "Graph Edge Coloring: A Survey",

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.",

keywords = "Adjacency lemma, Chromatic index, Edge coloring",

author = "Yan Cao and Guantao Chen and Guangming Jing and Michael Stiebitz and Bjarne Toft",

note = "Funding Information: G. Chen: Partially supported by NSFC grant 11871239. Publisher Copyright: {\textcopyright} 2019, Springer Japan KK, part of Springer Nature.",

year = "2019",

month = jan,

day = "2",

doi = "10.1007/s00373-018-1986-5",

language = "English (US)",

volume = "35",

pages = "33--66",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "1",

}

TY - JOUR

T1 - Graph Edge Coloring

T2 - A Survey

AU - Cao, Yan

AU - Chen, Guantao

AU - Jing, Guangming

AU - Stiebitz, Michael

AU - Toft, Bjarne

PY - 2019/1/2

Y1 - 2019/1/2

N2 - 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.

AB - 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.

KW - Adjacency lemma

KW - Chromatic index

KW - Edge coloring

UR - http://www.scopus.com/inward/record.url?scp=85059644259&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85059644259&partnerID=8YFLogxK

U2 - 10.1007/s00373-018-1986-5

DO - 10.1007/s00373-018-1986-5

M3 - Article

AN - SCOPUS:85059644259

SN - 0911-0119

VL - 35

SP - 33

EP - 66

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 1

ER -

Graph Edge Coloring: A Survey

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this