Many challenging problems in graph theory involve at least one of the
following four invariants:
(i) the stability number a (G) (also called the independence number),
defined as the largest number of pairwise nonadjacent vertices in G;
(ii) the clique covering number 8(G), defined as the least number of cliques
which cover all the vertices of G;
(iii) the clique number w(G), defined as the largest number of pairwise
adjacent vertices in G;
(iv) the chromatic number y(G) (sometimes denoted also by x(G)), defined
as the least number of colors needed to color all the vertices in such a way that
no two adjacent vertices have the same color.
The inequality a (G) S O(G) holds trivially for all graphs G: if k cliques cover
all the vertices then no more than k vertices can be pairwise nonadjacent. (A
similar observation shows that w(G)S y(G). In fact, if G denotes the complement
of G then o(G) = a (G) and y(G) = 8(C?).) Graphs which satisfy this
inequality with the equality sign played an important role in Claude Shannon’s
1956 paper concerning the ‘zero error capacity of a noisy channel’. In this paper,
Shannon remarked that the smallest graph G with a(G)< 8(G) is G, the cycle
of length five.