On the minimal number of edges in color-critical graphs

DOI10.1007/BF01215921zbMath0902.05025OpenAlexW1978379258MaRDI QIDQ1272188

Michael Krivelevich

Publication date: 24 November 1998

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01215921

zbMATH Keywords

extremal graph theorychromatic critical graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Related Items (22)

A better lower bound on average degree of 4-list-critical graphs ⋮ On the minimum number of edges in triangle-free 5-critical graphs ⋮ Lower Bounds for On-line Graph Colorings ⋮ Structure in sparse \(k\)-critical graphs ⋮ Bounds on Ramsey games via alterations ⋮ On Density of \(\boldsymbol{\mathbb{Z}_3}\) -Flow-Critical Graphs ⋮ Various bounds on the minimum number of arcs in a \(k\)-dicritical digraph ⋮ A new lower bound on the number of edges in colour-critical graphs and hypergraphs ⋮ On the concentration of the chromatic number of random graphs ⋮ Ore's conjecture on color-critical graphs is almost true ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ On the number of edges in hypergraphs critical with respect to strong colourings ⋮ Almost all graphs with high girth and suitable density have high chromatic number ⋮ Critically paintable, choosable or colorable graphs ⋮ A Brooks-type result for sparse critical graphs ⋮ Independent sets in \(n\)-vertex \(k\)-chromatic \(\ell \)-connected graphs ⋮ Improved lower bounds on the number of edges in list critical and online list critical graphs ⋮ The concentration of the chromatic number of random graphs ⋮ A list version of Dirac's theorem on the number of edges in colour-critical graphs ⋮ Large cliques and independent sets all over the place ⋮ On list critical graphs ⋮ Colour-critical graphs with few edges

Cites Work

• Unnamed Item
• Unnamed Item
• On coloring graphs with locally small chromatic number
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• On constructive methods in the theory of colour-critical graphs
• Graphs without large triangle free subgraphs
• A note on the sharp concentration of the chromatic number of random graphs
• Local and global clique numbers
• Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs
• Colour-critical graphs and hypergraphs
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• K^s-Free Graphs Without Large K^r-Free Subgraphs
• Bounding Ramsey numbers through large deviation inequalities
• 4-chromatic projective graphs
• Representations of integers as the sum of k terms
• The Construction of Certain Graphs

This page was built for publication: On the minimal number of edges in color-critical graphs