Four proofs of the directed Brooks' theorem

DOI10.1016/J.DISC.2022.113193MaRDI QIDQ6091815zbMATH OpenOpenAlexWikidataFDO

Authors 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

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

Abstract: We give four new proofs of the directed version of Brook's Theorem and an NP-completeness result.

Cites work

• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• A Note on Graphs of Dichromatic Number 2
• A different short proof of Brooks' theorem
• A flow theory for the dichromatic number
• A note on coloring digraphs of large girth
• Brooks' Theorem and Beyond
• Circular colorings of edge-weighted graphs
• Coloring dense digraphs
• Cuts in matchings of 3-connected cubic graphs
• Decomposing and colouring some locally semicomplete digraphs
• Dichromatic number and forced subdivisions
• Digraphs and variable degeneracy
• Eigenvalues and colorings of digraphs
• Extension of Gyárfás-Sumner conjecture to digraphs
• Forcing large transitive subtournaments
• Gallai's theorem for list coloring of digraphs
• Hajós and Ore constructions for digraphs
• List coloring digraphs
• On Brooks' theorem and some related results.
• On coloring digraphs with forbidden induced subgraphs
• On the dichromatic number of surfaces
• Planar digraphs of digirth four are 2-colorable
• Subdivisions in digraphs of large out-degree or large dichromatic number
• The circular chromatic number of a digraph
• The dichromatic number of a digraph
• The edge density of critical digraphs
• The minimum number of edges in 4-critical digraphs of given order
• Three short proofs in graph theory
• Two results on the digraph chromatic number

Cited in

(2)

• Various bounds on the minimum number of arcs in a \(k\)-dicritical digraph
• Topological properties and computation of silicate networks using graph-invariants

This page was built for publication: Four proofs of the directed Brooks' theorem

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