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.
Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-18576 |
Date | 01 August 2009 |
Creators | Nigussie, Yared |
Publisher | Digital Commons @ East Tennessee State University |
Source Sets | East Tennessee State University |
Detected Language | English |
Type | text |
Source | ETSU Faculty Works |
Page generated in 0.0021 seconds