A unified proof of Brooks' theorem and Catlin's theorem

DOI10.1016/J.DISC.2014.10.005zbMATH Open1302.05061arXiv1402.6298OpenAlexW2059026176MaRDI QIDQ472980FDOQ472980

Authors: Vaidy Sivaraman 

Publication date: 20 November 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We give a new proof of Brooks' theorem that immediately implies a strengthening of Brooks' theorem, known as Catlin's theorem.

Full work available at URL: https://arxiv.org/abs/1402.6298

Recommendations

• Brooks' Theorem and Beyond
• Brooks' theorem for generalized dart graphs
• Publication:4890132
• The colour theorems of Brooks and Gallai extended
• A strengthening of Brooks' theorem

zbMATH Keywords

chromatic numberBrooks' theoremindependent setCatlin's theorem

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Brooks' graph-coloring theorem and the independence number
• Title not available (Why is that?)
• Three short proofs in graph theory
• Vertex arboricity and maximum degree
• A short proof of Catlin's extension of Brooks' theorem
• A different short proof of Brooks' theorem
• On Brooks' theorem and some related results.

Cited In (5)

• Unifying the little Picard, Lohwater-Pommerenke and Brody theorems
• A note on graph coloring extensions and list-colorings
• Title not available (Why is that?)
• Brooks' theorem via the Alon-Tarsi theorem
• Brooks' Theorem and Beyond

This page was built for publication: A unified proof of Brooks' theorem and Catlin's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q472980)