Upper-critical graphs
Jose Antonio Mart · arXiv (Cornell University) · 2010
This work introduces the concept of upper-critical graphs, in a complementary way of the conventional (lower)critical graphs: an element x of a graph G is called critical if �(G− x) < �(G). It is said that G is a critical graph if every element (vertex or edge) of G is critical. Analogously, a graph G is called upper-critical if there is no edge that can be added to G such that G preserves its chromatic number, i.e.f e2E(G)j�(G + e) = �(G)g=; . A characterization in terms of hereditary properties under some transformations, e.g. subgraphs and minors and in terms of construction and counting is given.