# 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.

Bibliography
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.