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.

Let K be a class of graphs. A pair (F,U) is a finite duality in K if U∈K, F is a finite set of graphs, and for any graph G in K we have G≤U if and only if F≤≰G for all F∈F, where "≤" is the homomorphism order. We also say U is a dual graph in K. We prove that the class of planar graphs has no finite dualities except for two trivial cases. We also prove that the class of toroidal graphs has no 5-colorable dual graphs except for two trivial cases. In a sharp contrast, for a higher genus orientable surface S we show that Thomassen's result (Thomassen, 1997 [17]) implies that the class, G(S), of all graphs embeddable in S has a number of finite dualities. Equivalently, our first result shows that for every planar core graph H except K1 and K4, there are infinitely many minimal planar obstructions for H-coloring (Hell and Nešetřil, 1990 [4]), whereas our later result gives a converse of Thomassen's theorem (Thomassen, 1997 [17]) for 5-colorable graphs on the torus.