A new lower bound on the number of edges in colour-critical graphs and hypergraphs (Q1405127)

A graph \(G\) is called \(k\)-critical if it has chromatic number \(k\), but every proper subgraph of \(G\) is \((k-1)\)-colorable. In this paper it is proved that every \(k\)-critical graph \((k\geq 6)\) on \(n\geq k+2\) vertices has at least \(\frac{1}{2}(k-1+\frac{k-3}{(k-c)(k-1)+k-3})n\) edges, where \(c=(k-5)\alpha _{k}\) and \(\alpha _{k}=\frac{1}{2}-\frac{1}{(k-1)(k-2)}\). This improves earlier bounds established by Gallai and by Krivelevich. Now let \(H\) be a hypergraph not containing a \(K_{k}\), and let \(\Phi \) be a list for \(H\) satisfying \(|\Phi (x)|=k-1\) for every \(x\in V(H)\). It is proved that if \(H\) is \(\Phi \)-critical, then the sum of the degrees of the vertices of \(H\) is bounded below by \((k-1+\frac{k-3}{(k-c)(k-1)+k-3})|V(H)|\) provided that \(k\geq 9\) and \(c=\frac{1}{3}(k-4)\alpha _{k}\) or \(k\geq 6\), \(\Phi (x)=\{1,\dots ,k-1\}\) for every \(x\in V(H)\) and \(c=(k-5)\alpha _{k}\).