Dirac's theorem on chordal graphs implies Brooks' theorem

DOI10.1016/J.DISC.2023.113791MaRDI QIDQ6136675zbMATH OpenFDO

Authors Carl Feghali

Publication date 17 January 2024

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

list coloringBrooks' theoremDirac's theorem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: We give yet another proof of Brooks' theorem, this time based on a famous theorem of Dirac concerning chordal graphs.

Recommendations

• A list version of Dirac's theorem on the number of edges in colour-critical graphs
• Brooks' Theorem and Beyond
• On a Lovász-type lemma, applied to Brooks' theorem for list-colouring
• Brooks' theorem via the Alon-Tarsi theorem
• A different short proof of Brooks' theorem

Cites work

• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Brooks' Theorem and Beyond
• On rigid circuit graphs
• Vertex partitions and maximum degenerate subgraphs

This page was built for publication: Dirac's theorem on chordal graphs implies Brooks' theorem

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