On color critical graphs with large adaptable chromatic numbers (Q1684934): Difference between revisions

In this paper the author constructs a \((k-1)\)-critical graph \(F_{k-1}\) with many subgraphs with adaptable chromatic number \(k-2\) using Hajós construction if there is a \((k-1)\)-critical graph \(G_{k-1}\) that contains a subgraph \(H_{k-1}\) such that \(\chi_{a}(H_k)\,=\,k-2\) and \(V(H_{k-1})\) is a proper subset of \(V(G_{k-1})\). Secondly if \(G\) is adaptably critical, then it is shown that \(\delta(G) \geq \chi_{a}(G)-1\). For \(k \geq 2\), let \(G\) be a graph such that \(\chi_{a}(G)\,=\,k-1\). Let \(G_i\) (\(i\,=\,1,2,\ldots,k-1\)) be \(k-1\) disjoint copies of \(G\). Let \(x\) be a new vertex. \(H\,=\,\{x\} \lor (\bigcup^{k-1}_{i=1}G_i)\). The author shows that \(H\) is a \(k\)-adaptably critical graph if the graph \(G\) is \((k-1)\)-adaptably critical. Several papers have answered partially the problems stated in the paper, for example [\textit{J. Goedgebeur} and \textit{O. Schaudt}, J. Graph Theory 87, No. 2, 188--207 (2018; Zbl 1380.05063)].