Vertex critical graphs with many extra edges
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
In addition, a vertex critical graph with chromatic number \( k\) is said to be a \( k\)vertexcritical 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\)vertexcritical 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\)vertexcritical graph with no critical edges. Recently, Jensen [3] showed that for any \( m\) and any \( k \geq 5\), there exists a \( k\)vertexcritical 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 nonprime integer \( k > 5\)
Further, in 2009, J. Wang [5] show that any \( k\)vertexcritial graph without any critical edge generates an infinite family of \( k\)vertexcritical graphs.
Bibliography  

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

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. 111116, NorthHolland, AmsterdamNew
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. 323330, 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.
