Upper-critical graphs

الأصل · EN

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. {e ∈ E(G) | χ(G+e) = χ(G) } =. We show that the class of upper-critical graphs is the same as the class of complete k-partite graphs. A characterization in terms of hereditary properties under some transformations, e.g. subgraphs and minors and in terms of construction and counting is given.