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 = K k − 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 K k -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 = K k − 2 + H ′ , (the join of a complete graph K k − 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.