On the edge-density of 4-critical graphs

DOI10.1007/s00493-009-2267-yzbMath1224.05170OpenAlexW2065653857MaRDI QIDQ624211

Babak Farzad, Michael S. O. Molloy

Publication date: 8 February 2011

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-009-2267-y

zbMATH Keywords

graph colouringcritical graphedge-densityGallai's conjecture

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Related Items

Ore's conjecture on color-critical graphs is almost true ⋮ The edge density of critical digraphs ⋮ A Brooks-type result for sparse critical graphs ⋮ Adynamic coloring of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Excess in critical graphs
• An improved bound on the minimal number of edges in color-critical graphs
• A new lower bound on the number of edges in colour-critical graphs and hypergraphs
• Colour-critical graphs with few edges
• Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• The number of edges in critical graphs.
• A new proof of a theorem of Dirac on the number of edges in critical graphs.
• On Dirac's Generalization of Brooks' Theorem

This page was built for publication: On the edge-density of 4-critical graphs