Vertex critical graphs with many extra edges

A graph is said to be vertex critical if the deletion of any vertex decreases the chromatic number by \( 1\).

In addition, a vertex critical graph with chromatic number \( k\) is said to be a \( k\)-vertex-critical graph.

Problem (proposed by Erdös [2])

For each \(k \geq 4\), is there some positive function \(f_k\) tending to infinity so that there exists a graph \(G\) on \(n\) vertices which is \(k\)-vertex-critical but with \(\chi(G -A) = k\) for any set \(A\) of at most \(f_k(n)\) edges?

In [2] Erdös asked: ``If there is such an \( f_k\), how fast can it grow?"

Brown [1] gave an example of a \( 5\)-vertex-critical graph with no critical edges. Recently, Jensen [3] showed that for any \( m\) and any \( k \geq 5\), there exists a \( k\)-vertex-critical graph such that the chromatic number is not decreased after deleting any \( m\) edges all incident to a common vertex.

Lattanzio [4] constructed \( k\)-vertex critical graphs with no critical edges for every non-prime integer \( k > 5\)

Further, in 2009, J. Wang [5] show that any \( k\)-vertex-critial graph without any critical edge generates an infinite family of \( k\)-vertex-critical graphs.

1 J. I. Brown, A vertex critical graph without critical edges, Discrete Math. 102 (1992), 99-101.

2 P. Erdös, On some aspects of my work with Gabriel Dirac, Graph theory in memory of G. A. Dirac (Sandbjerg, 1985), Ann. Discrete Math., 41, pp. 111-116, North-Holland, Amsterdam-New York, 1989.

3 T. R. Jensen, Structure of Critical Graphs, Ph. D. Thesis, Odense University, Denmark, 1996.

4 J.J. Lattanzio, A Note on a Conjecture of Dirac. Discrete Math. 258, pp. 323-330, 2002.

5 J. Wang Infinite Family from Each Vertex \( k\)-Critical Graph without Any Critical Edge Combinatorial Optimization and Applications Lecture Notes in Computer Science 5573 pp.  238- 248 Springer Berlin, Heidelberg, 2009.