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

DOI10.1016/J.DISC.2014.10.005MaRDI QIDQ472980zbMATH OpenOpenAlexFDO

Authors Vaidy Sivaraman

Publication date 20 November 2014

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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

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

Cites work

• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• A different short proof of Brooks' theorem
• A short proof of Catlin's extension of Brooks' theorem
• Brooks' graph-coloring theorem and the independence number
• On Brooks' theorem and some related results.
• Three short proofs in graph theory
• Vertex arboricity and maximum degree

Cited in

(6)

• scientific article; zbMATH DE number 915265 (Why is no real title available?)
• A Catlin-type theorem for graph partitioning avoiding prescribed subgraphs
• Unifying the little Picard, Lohwater-Pommerenke and Brody theorems
• Brooks' theorem via the Alon-Tarsi theorem
• Brooks' Theorem and Beyond
• A note on graph coloring extensions and list-colorings

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)