Critical graphs with large minimum degree
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.
Is it true that \(g(n,4) \geq cn\) for some constant \(c\)?
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.
A problem on critical graphs with large degree (proposed by Erdös [1] [2])
Let \(g(n,k)\) denote the maximum value \(m\) such that there exists a \(k\)critical graph on \(n\) vertices with minimum degree at least \(m\). What is the magnitude of \(g(n,k)\)?Is it true that \(g(n,4) \geq cn\) for some constant \(c\)?
Simonovits [3] and Toft [4] proved that \( g(n,4) \geq c n^{1/3}\).
As of 2011, there has been little progress on this problem.
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.

2 
P. Erdös, Problems and results in combinatorial analysis and
combinatorial number theory, Graph theory, combinatorics and
applications, Vol. 1 (Kalamazoo, MI, 1988), WileyIntersci. Publ.,
397406, Wiley, New York, 1991.

3 
M. Simonovits, On colourcritical graphs,
Studia Sci. Math. Hungar. 7 (1972), 6781.

4  B. Toft, Two theorems on critical \( 4\)chromatic graphs, Studia Sci. Math. Hungar. 7 (1972), 8389. 