Dirac's theorem on chordal graphs implies Brooks' theorem

DOI10.1016/J.DISC.2023.113791arXiv2307.00640MaRDI QIDQ6136675FDOQ6136675

Authors: Carl Feghali 

Publication date: 17 January 2024

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

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

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

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

zbMATH Keywords

list coloringBrooks' theoremDirac's theorem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On rigid circuit graphs
• Brooks' Theorem and Beyond
• 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)