Yet another proof for Brooks' theorem

Tamás Fleiner


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

chromatic number, greedy coloring, DFS tree

Bibtex entry:

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: 13.3.2018. Please email your comments to Tamás Király!