Extended Gallai's Theorem

Let G and H be graphs. We say G is H-critical, if every proper subgraph of G except G itself is homomorphic to H. This generalizes the widely known concept of k-color-critical graphs, as they are the case H=Kk−1. In 1963 [T. Gallai, Kritiche Graphen, I., Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963), 373-395], Gallai proved that the vertices of degree k in a Kk-critical graph induce a subgraph whose blocks are either odd cycles or complete graphs. We generalize Gallai's Theorem for every H-critical graph, where H=Kk−2+H′, (the join of a complete graph Kk−2 with any graph H′). This answers one of the two unknown cases of a problem given in [J. Nešetřil, Y. Nigussie, Finite dualities and map-critical graphs on a fixed surface. (Submitted to Journal of Combin. Theory, Series B)]. We also propose an open question, which may be a characterization of all graphs for which Gallai's Theorem holds.