Prove or disprove that every graph $G$ satisfies $\chi (G) \le |G| - \alpha (G) + 1$

992 Views Asked by At

Every graph $G$ satisfies $\chi (G) \le |G| - \alpha (G) + 1$.

Where $\alpha (G)$ is the maximum size of an independent set of vertices of $G$/

I have tested this with multiple examples and it seems to work, but I am not sure how I would go about proving this. Any help is appreciated

1

There are 1 best solutions below

0
On BEST ANSWER

Take a maximal independent set and color it with one color. Color each of the remaining $|G|-\alpha(G)$ vertices its own color. This is a valid coloring, with $|G|-\alpha(G)+1$ colors.