Various bounds on the minimum number of arcs in a \(k\)-dicritical digraph

DOI10.37236/11549arXiv2208.02112OpenAlexW4391258580MaRDI QIDQ6117430

Pierre Aboulker, Quentin Vermande

Publication date: 19 February 2024

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2208.02112

zbMATH Keywords

number of connected componentsminor-verticescritical \(k\)-chromatic graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ore's conjecture for \(k=4\) and Grötzsch's theorem
• Ore's conjecture on color-critical graphs is almost true
• Eigenvalues and colorings of digraphs
• On the minimal number of edges in color-critical graphs
• Color-critical graphs on a fixed surface
• The dichromatic number of a digraph
• Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs
• Coloring hypergraphs of low connectivity
• The minimum number of edges in 4-critical digraphs of given order
• Hajós and Ore constructions for digraphs
• Gallai's Theorem for List Coloring of 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
• Four proofs of the directed Brooks' theorem

This page was built for publication: Various bounds on the minimum number of arcs in a \(k\)-dicritical digraph