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

DOI10.1007/S00373-020-02147-YMaRDI QIDQ2175801zbMATH OpenOpenAlexFDO

Authors Michael Stiebitz, Alexandr 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

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

Review text

The authors consider the problem of finding critical graphs for coloring of directed graphs, the model defined by \textit{V. Neumann-Lara} [J. Comb. Theory, Ser. B 33, 265--270 (1982; Zbl 0506.05031)]. The dichromatic number \(\chi(D)\) of a directed graph \(D\) is the smallest number \(k\) for which \(D\) has a coloring such that each vertex receives a color and no directed cycle of \(D\) is monochromatic (acyclic coloring). Let \(d_k(n)\) denote the number of the minimum number of arc possible in a \(k\)-critical digraph of order \(n\). The paper gives proof that \(d_4(n) \geq \lceil (10n-4)/3\rceil\) for all \(n\geq 4\) and \(n\not = 5\). The results presented in the paper complete the knowledge in the subject under consideration. Up to know the problem of \(k\)-critical graphs for coloring of directed graphs were known for \(k\leq 3\). Thus, the contribution is significant.

Recommendations

• Hajós and Ore constructions for digraphs
• The 3 and 4-dichromatic tournaments of minimum order
• Vertex critical r-dichromatic tournaments
• scientific article; zbMATH DE number 3918396
• Dichromatic number, circulant tournaments and Zykov sums of 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
• Brook's theorem
• Color-critical graphs and hypergraphs with few edges: a survey
• Eigenvalues and colorings of digraphs
• Graphs on surfaces
• Hajós and Ore constructions for digraphs
• scientific article; zbMATH DE number 3687449 (Why is no real title available?)
• scientific article; zbMATH DE number 3232667 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• Ore's conjecture for k=4 and Grötzsch's theorem
• Ore's conjecture on color-critical graphs is almost true
• Planar digraphs of digirth four are 2-colorable
• Strengthened Brooks' theorem for digraphs of girth at least three
• The 3 and 4-dichromatic tournaments of minimum order
• The \(m\)-degenerate chromatic number of a digraph
• The circular chromatic number of a digraph
• The dichromatic number of a digraph
• The number of edges in critical graphs.
• The structure of k-chromatic graphs

Cited in

(17)

• The 3 and 4-dichromatic tournaments of minimum order
• Extension of Gyárfás-Sumner conjecture to digraphs
• On the dichromatic number of surfaces
• Hajós and Ore constructions for digraphs
• Decomposing and colouring some locally semicomplete digraphs
• On the Minimum Edge‐Density of 4‐Critical Graphs of Girth Five
• The edge density of critical digraphs
• On deeply critical oriented cliques
• 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
• Minimum number of arcs in k-critical digraphs with order at most 2k-1
• On the minimum number of arcs in \(k\)-dicritical oriented graphs
• On the dichromatic number of surfaces
• On the minimum number of arcs in 4-dicritical oriented graphs
• The 3-dicritical semi-complete digraphs
• Clique number of tournaments

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

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