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

DOI10.1137/23M1553753zbMATH Open1542.05063MaRDI QIDQ6561323FDOQ6561323

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)

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

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)

Cites Work

• The circular chromatic number of a digraph
• Title not available (Why is that?)
• Eigenvalues and colorings of digraphs
• The dichromatic 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the number of edges in colour-critical graphs and hypergraphs
• Decomposing a graph into forests
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• Title not available (Why is that?)
• The 3 and 4-dichromatic tournaments of minimum order
• The edge density of critical digraphs
• On the Minimum Edge‐Density of 4‐Critical Graphs of Girth Five
• Title not available (Why is that?)
• On the minimum number of edges in triangle-free 5-critical graphs
• The minimum number of edges in 4-critical digraphs of given order
• Hajós and Ore constructions for digraphs
• The smallest 5-chromatic tournament
• Various bounds on the minimum number of arcs in a \(k\)-dicritical digraph

Cited In (4)

• 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
• On the minimum number of arcs in 4-dicritical oriented graphs
• Various bounds on the minimum number of arcs in a \(k\)-dicritical digraph

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)