On color critical graphs (Q1059085)

The graph G is said to be \((k+1)\)-critical if its chromatic number is \(k+1\) but the chromatic number of every proper subgraph G' of G (i.e., E(G')\(\subset E(G))\) is \(\leq k\). In this paper it is proved that the minimal number of edges which have to be omitted from a \((k+1)\)-critical graph on n vertices in order to make it bipartite is at least \(\left( \begin{matrix} k\\ 2\end{matrix} \right)\) for n large enough and for every n there exists a \((k+1)\)-critical graph G, \(| V(G)| >n\) which can be made bipartite by the omission of \(\left( \begin{matrix} k\\ 2\end{matrix} \right)\) edges. Also, it is shown the existence of a function f(k,p) such that for any n there is a \((k+1)\)-critical graph with more than n vertices, girth greater than p which can be made bipartite by the omission of \(\leq f(k,p)\) edges. The authors investigate some other similar questions: critical graphs with a very long induced path and chromatic graphs satisfying symmetry properties (e.g., graphs with transitive automorphism group).