The edge density of critical digraphs

DOI10.1007/S00493-014-2862-4zbMATH Open1374.05103OpenAlexW2077882202MaRDI QIDQ519953FDOQ519953

Ken-ichi Kawarabayashi, Richard Hoshino

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

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

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)

Cites Work

• Two results on the digraph chromatic number
• The circular chromatic number of a digraph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Eigenvalues and colorings of digraphs
• The dichromatic number of a digraph
• Ore's conjecture on color-critical graphs is almost true
• On the edge-density of 4-critical graphs
• A new lower bound on the number of edges in colour-critical graphs and hypergraphs
• Title not available (Why is that?)
• Ramsey-type theorems
• The Eigenvalues of a Graph and Its Chromatic Number
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Chromatic number, girth and maximal degree
• Tournaments and colouring
• Circular colorings of edge-weighted graphs
• Title not available (Why is that?)
• Gallai's Theorem for List Coloring of Digraphs
• The 3 and 4-dichromatic tournaments of minimum order
• A conjecture of Neumann-Lara on infinite families of \(r\)-dichromatic circulant tournaments
• Dense critical and vertex-critical graphs

Cited In (10)

• Hajós and Ore constructions for digraphs
• On the minimum number of arcs in \(k\)-dicritical oriented graphs
• 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
• Digraphs and Variable Degeneracy

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)