Upper-critical graphs

Abstract

This work introduces the concept of \emph{upper-critical graphs}, in a complementary way of the conventional (lower)critical graphs: an element $x$ of a graph $G$ is called \emph{critical} if $\chi (G-x)<\chi (G)$. It is said that $G$ is a \emph{critical graph} if every element (vertex or edge) of $G$ is critical. Analogously, a graph $G$ is called \emph{upper-critical} if there is no edge that can be added to $G$ such that $G$ preserves its chromatic number, i.e. \{$e\in E(\bar{G})|\chi (G+e)=\chi (G)$ \} $=$ $\varnothing$. 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.