2018/05/28 by Mariusz Zając, Zając, Mariusz
Computer Science · #05C15 (Primary) #68R10 (Secondary) #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1805.11176
openalex publication_date 2018/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give a simple short proof of Brooks' theorem using only induction and greedy coloring, while avoiding issues of graph connectivity. The argument generalizes easily to some extensions of Brooks' theorem, including its variants for list coloring, signed graphs coloring and correspondence coloring.