QP-2014-01

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.

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 egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2014},
NUMBER	=	{QP-2014-01}

}