Gallai's problem on Dirac's construction
Let a graph \(K\) consist of disjoint graphs \(G\) and \(H\) and a set of edges joining \(G\) and \(H\). If each of \(G\), \(H\), and \(K\) are color-critical, when is every vertex of \(G\) joined to every vertex of \(H\) (i.e. \(K=G+H)?\) This does occur, for example, if \(G\) and \(H\) are both complete. In this paper a small selection of such color-critical graphs \(G\), \(H\), and \(K\) is presented for which \(K\neq G+H\).
scientific article; zbMATH DE number 89915