Size, chromatic number, and connectivity (Q1340118)

Let \(g(n,k,c)\) denote the minimum number of edges in a \(k\)-edge-connected graph having order \(n\) and chromatic number at least \(c\) (\(n> k\), \(n\geq c\)). A graph is vertex -- \(c\)-critical if \(\chi(G)= c\) and \(\chi(G- v)= c-1\) for every \(v\in V(G)\); \(G\) is \(c\)-critical if it is vertex -- \(c\)- critical and also \(\chi(G- e)= c-1\) for every \(e\in E(G)\). Theorem 1. Every connected \(c\)-chromatic \(n\)-vertex graph has at least \((\begin{smallmatrix} c\\ 2\end{smallmatrix})+ n- c\) edges, and this is best possible. Theorem 2. If \(n> c> k\geq 3\), then \(g(n, k,c)\geq (\begin{smallmatrix} c\\ 2\end{smallmatrix})+ \lceil\frac{(n+ 1-c)}2\rceil\), except \(g(n,k,c)= (\begin{smallmatrix} c\\ 2\end{smallmatrix})+ \frac{(n+1- c)} 2-1\) if \(c= k+1\), and there is a \(c\)-critical \(n\)-vertex graph with \(\frac{(c- 1)(n+1)} 2- 1\) edges. Theorem 3. If \(n\geq c+k\) and \(c\geq k\geq 2\), then \(g(n,k, c)\leq (\begin{smallmatrix} c\\ 2\end{smallmatrix})+ \lceil \frac{k(n+ 1- c)}2\rceil\). Theorem 4. If \(c\leq \lceil\frac{k+ 1}2\rceil\), or if \(c\leq k\) and \(n> k+ c\), then \(g(n,k,c)= \lceil\frac{kn} 2\rceil\).