Upper-critical graphs

Details Upper-critical graphs Upper-critical graphs

2010-11-18

arxiv.org/abs/1011.4124v4

Mathematics

Combinatorics

Scientific paper

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)$ \} $=$ $\emptyset$. 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.

Affiliated with

Also associated with

No associations

Rating

Upper-critical graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Upper-critical graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Upper-critical graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-536330