Prove that for every graph G, X(G) <= n(G) - &(G) + 1.

Let X(G) denote the chromatic number of G

Let n(G) denote the number of vertices of G

Let &(G) denote the max size of an indepent set of vertives in G

Printable View

- Nov 14th 2010, 10:56 PMjzelltChromatic number of G
Prove that for every graph G, X(G) <= n(G) - &(G) + 1.

Let X(G) denote the chromatic number of G

Let n(G) denote the number of vertices of G

Let &(G) denote the max size of an indepent set of vertives in G