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)

zbMATH Keywords

digraphdichromatic number

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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

(4)

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

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)