Four proofs of the directed Brooks' theorem

DOI10.1016/j.disc.2022.113193zbMath1527.05056arXiv2109.01600OpenAlexW3198214633WikidataQ114671063 ScholiaQ114671063MaRDI QIDQ6091815

Pierre Aboulker, Guillaume Aubian

Publication date: 27 November 2023

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

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

zbMATH Keywords

dichromatic numberBrooks theoremcolouring digraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items

Various bounds on the minimum number of arcs in a \(k\)-dicritical digraph

Cites Work

• Unnamed Item
• Unnamed Item
• Two results on the digraph chromatic number
• The edge density of critical digraphs
• Eigenvalues and colorings of digraphs
• Three short proofs in graph theory
• Cuts in matchings of 3-connected cubic graphs
• The dichromatic number of a digraph
• A note on coloring digraphs of large girth
• Extension of Gyárfás-Sumner conjecture to digraphs
• Dichromatic number and forced subdivisions
• On the dichromatic number of surfaces
• The minimum number of edges in 4-critical digraphs of given order
• Hajós and Ore constructions for digraphs
• Subdivisions in digraphs of large out-degree or large dichromatic number
• Forcing large transitive subtournaments
• A flow theory for the dichromatic number
• A different short proof of Brooks' theorem
• Decomposing and colouring some locally semicomplete digraphs
• Gallai's Theorem for List Coloring of Digraphs
• Brooks' Theorem and Beyond
• Circular colorings of edge-weighted graphs
• The circular chromatic number of a digraph
• List coloring digraphs
• On Brooks' theorem and some related results.
• A Note on Graphs of Dichromatic Number 2
• Digraphs and Variable Degeneracy
• Planar Digraphs of Digirth Four are 2-Colorable
• Coloring dense digraphs
• On coloring digraphs with forbidden induced subgraphs