Four proofs of the directed Brooks' theorem

DOI10.1016/J.DISC.2022.113193zbMATH Open1527.05056arXiv2109.01600OpenAlexW3198214633WikidataQ114671063 ScholiaQ114671063MaRDI QIDQ6091815FDOQ6091815

Pierre Aboulker, Guillaume Aubian

Publication date: 27 November 2023

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

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

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)

Cites Work

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

Cited In (2)

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

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)