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\)-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.
|