Some remarks on \((k-1)\)-critical subgraphs of \(k\)-critical graphs (Q1906843)

The paper investigates \((k- 1)\)-critical subgraphs of \(k\)-critical graphs (a graph is \(k\)-critical if it has chromatic number \(k\) but every proper subgraph is \((k- 1)\)-colorable). Main result is an improved bound on the minimum number \(f_k(n)\) of \((k- 1)\)-critical subgraphs of \(k\)-critical graphs of order \(n\), giving \({f_k(n)\choose k- 1}\geq n\text{ for } n> k+ 1\geq 5\). Further it is shown that for a given \(k\)-critical graph \(G\) the number \(f_k(G)\) of \((k- 1)\)-critical subgraphs of \(G\) and the maximum order \(g_k(G)\) of such \((k- 1)\)-critical subgraph of \(G\) satisfy \(f_k(G)\cdot g_k(G)\geq n(k- 1)\). Especially for \(k= 4\) asymptotic bounds are given for \(F_k(n)\), the maximum number of \((k- 1)\)-critical subgraphs of \(k\)-critical graphs of order \(n\).