The minimum number of edges in 4-critical digraphs of given order

DOI10.1007/s00373-020-02147-yzbMath1441.05080OpenAlexW3006087353MaRDI QIDQ2175801

Michael Stiebitz, Alexandr V. Kostochka

Publication date: 30 April 2020

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-020-02147-y

zbMATH Keywords

average degreecoloring graphs and digraphscritical graphs and digraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items (6)

On the dichromatic number of surfaces ⋮ Decomposing and colouring some locally semicomplete digraphs ⋮ The smallest 5-chromatic tournament ⋮ Four proofs of the directed Brooks' theorem ⋮ Various bounds on the minimum number of arcs in a \(k\)-dicritical digraph ⋮ Extension of Gyárfás-Sumner conjecture to digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The \(m\)-degenerate chromatic number of a digraph
• Ore's conjecture for \(k=4\) and Grötzsch's theorem
• Ore's conjecture on color-critical graphs is almost true
• Strengthened Brooks' theorem for digraphs of girth at least three
• Eigenvalues and colorings of digraphs
• The 3 and 4-dichromatic tournaments of minimum order
• The dichromatic number of a digraph
• Hajós and Ore constructions for digraphs
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• The number of edges in critical graphs.
• The circular chromatic number of a digraph
• Planar Digraphs of Digirth Four are 2-Colorable
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• The structure of k-chromatic graphs

This page was built for publication: The minimum number of edges in 4-critical digraphs of given order