Dense critical and vertex-critical graphs (Q1850041)

In this paper it is proved for \(4\leq k\leq d\) that there exists a constant \(c_{k,d}\) such that infinitely many \(k\)-chromatic critical graphs have minimum degree at least \(d\) and at least \(c_{k,d}n^{2}\) edges, where \(n\) is the order of the graph. Also a general bound \(c_{k,d}\geq cd^{-4}\) for infinitely many values of \(d\) is derived. It is shown for \(k\geq 3\) that there exists an infinite family of vertex-critical \(k\)-chromatic graphs containing at least \(((k-3)n^{2}+(k+1)n)/(2(k-1))\) edges, and for every \(k\geq 5\) and every \(m>0\) that there exists a vertex-critical \(k\)-chromatic graph such that any subgraph remaining after deletion of a set of \(m\) edges incident with the same vertex is again \(k\)-chromatic. This extends a result of \textit{J. I. Brown} [Discrete Math. 102, 99-102 (1992; Zbl 0768.05038)], who proved this statement for \(k=5\) and \(m=1\), thereby answering a problem by Dirac whether there exists a vertex-critical graph without critical edges. Dirac's original question for \(k=4\) remains unsolved, however.