On the minimum number of arcs in k-dicritical oriented graphs

DOI10.1137/23M1553753MaRDI QIDQ6561323zbMATH OpenFDO

Authors Pierre Aboulker, Thomas Bellitto, Frédéric Havet, Clément Rambaud

Publication date 25 June 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/23M1553753

zbMATH Keywords

dichromatic numberdigraph

Mathematics Subject Classification ID

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

Recommendations

• On the minimum number of arcs in 4-dicritical oriented graphs
• Various bounds on the minimum number of arcs in a k-dicritical digraph
• The minimum number of edges in 4-critical digraphs of given order
• Minimum number of arcs in k-critical digraphs with order at most 2k-1
• Hajós and Ore constructions for digraphs

Cites work

• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• Decomposing a graph into forests
• Eigenvalues and colorings of digraphs
• Hajós and Ore constructions for digraphs
• scientific article; zbMATH DE number 1303523 (Why is no real title available?)
• scientific article; zbMATH DE number 3232667 (Why is no real title available?)
• scientific article; zbMATH DE number 3258078 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• On the Minimum Edge‐Density of 4‐Critical Graphs of Girth Five
• On the minimum number of edges in triangle-free 5-critical graphs
• On the number of edges in colour-critical graphs and hypergraphs
• Ore's conjecture for k=4 and Grötzsch's theorem
• Ore's conjecture on color-critical graphs is almost true
• The 3 and 4-dichromatic tournaments of minimum order
• 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
• The smallest 5-chromatic tournament
• Various bounds on the minimum number of arcs in a k-dicritical digraph

Cited in

(5)

• Various bounds on the minimum number of arcs in a k-dicritical digraph
• Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring
• Minimum number of arcs in k-critical digraphs with order at most 2k-1
• On the minimum number of arcs in 4-dicritical oriented graphs
• The 3-dicritical semi-complete digraphs

This page was built for publication: On the minimum number of arcs in \(k\)-dicritical oriented graphs

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