Estimate the maximum number of edges for a \(k\)critical graph on n vertices
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
A graph is said to be edge critical
if the deletion of any edge decreases the chromatic number by \( 1\).
Analogously, a graph is said to be vertex critical
if
the deletion of any vertex decreases the chromatic number by \( 1\).
Here we use the convention that a critical graph means an edge
critical graph.
A critical graph with chromatic number \( k\) is said to be a \( k\)critical graph. Similarly, a vertex critical graph with chromatic number \( k\) is said to be a \( k\)vertexcritical graph.
Problem [1], (1949)
What is the largest number \(m\), denoted by \(f(n,k)\), such that there is a \(k\)critical graph on \(n\) vertices and \(m\) edges? In particular, determine \[ \lim_{n \rightarrow \infty} \frac{f(n,k)}{n^2} = c_k. \]
Bibliography  

1 
P. Erdös, Problems and results on chromatic numbers in finite
and infinite graphs, Graph theory with applications to
algorithms and computer science (Kalamazoo, MI, 1984), WileyIntersci.
Publ., 201213, Wiley, New York, 1985.
