QP-2014-01

Yet another proof for Brooks' theorem

Tamás Fleiner



Abstract

We give a proof for Brooks' theorem on the chromatic number of graphs based on well-known properties of DFS trees.


Keywords:
chromatic number, greedy coloring, DFS tree


Bibtex entry:

@techreport{egresqp-14-01,
AUTHOR = {Fleiner, Tam{\'a}s},
TITLE = {Yet another proof for Brooks' theorem},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2014},
NUMBER = {QP-2014-01}
}


Last modification: 21.9.2017. Please email your comments to Tamás Király!