The edge density of critical digraphs

DOI10.1007/S00493-014-2862-4zbMath1374.05103OpenAlexW2077882202MaRDI QIDQ519953

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Related Items (6)

Digraphs and Variable Degeneracy ⋮ Decomposing and colouring some locally semicomplete digraphs ⋮ The smallest 5-chromatic tournament ⋮ Four proofs of the directed Brooks' theorem ⋮ Extension of Gyárfás-Sumner conjecture to digraphs ⋮ Hajós and Ore constructions for digraphs

Cites Work

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

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