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\)-vertex-critical 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), Wiley-Intersci.
Publ., 201-213, 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), Wiley-Intersci. Publ.,
397-406, Wiley, New York, 1991.
|
3 |
M. Simonovits, On colour-critical graphs,
Studia Sci. Math. Hungar. 7 (1972), 67-81.
|
4 | B. Toft, Two theorems on critical \( 4\)-chromatic graphs, Studia Sci. Math. Hungar. 7 (1972), 83-89. |