The edge density of critical digraphs

DOI10.1007/S00493-014-2862-4MaRDI QIDQ519953zbMATH OpenOpenAlexFDO

Authors Richard Hoshino, Ken-ichi Kawarabayashi

Publication date 31 March 2017

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-014-2862-4

zbMATH Keywords

chromatic numberedge density\(k\)-chromatic\(k\)-criticalcirculant tournamentcritical digraphdigirth

Mathematics Subject Classification ID

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

Recommendations

• Hajós and Ore constructions for digraphs
• Digraph girth via chromatic number
• The minimum number of edges in 4-critical digraphs of given order
• Dichromatic number, circulant tournaments and Zykov sums of digraphs
• Dense critical and vertex-critical graphs

Cites work

• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 3361909 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• A conjecture of Neumann-Lara on infinite families of \(r\)-dichromatic circulant tournaments
• A new lower bound on the number of edges in colour-critical graphs and hypergraphs
• Chromatic number, girth and maximal degree
• Circular colorings of edge-weighted graphs
• Dense critical and vertex-critical graphs
• Eigenvalues and colorings of digraphs
• Gallai's theorem for list coloring of digraphs
• On the edge-density of 4-critical graphs
• Ore's conjecture on color-critical graphs is almost true
• Ramsey-type theorems
• The 3 and 4-dichromatic tournaments of minimum order
• The Eigenvalues of a Graph and Its Chromatic Number
• The circular chromatic number of a digraph
• The dichromatic number of a digraph
• Tournaments and colouring
• Two results on the digraph chromatic number

Cited in

(10)

• Hajós and Ore constructions for digraphs
• On the minimum number of arcs in \(k\)-dicritical oriented graphs
• Digraphs and variable degeneracy
• Extension of Gyárfás-Sumner conjecture to digraphs
• On the edge-density of 4-critical graphs
• Edge distribution and density in the characteristic sequence
• On the density of \(C_7\)-critical graphs
• The smallest 5-chromatic tournament
• Decomposing and colouring some locally semicomplete digraphs
• Four proofs of the directed Brooks' theorem

This page was built for publication: The edge density of critical digraphs

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