Upper bound for the sum of chromatic number of a graph and chromatic number of its complement

836 Views Asked by At

I need to prove that for any simple graph $G$ on $n$ vertices the following inequality is true: $\chi(G)+\chi(\overline {G}))\le n+1$; where $G$ is a simple graph, $\overline{G}$ its complement, $\chi(G)$ the chromatic number. To prove this bound I used the inequality $\chi(G)\le\Delta+1$. But I am faced with a problem because in this way of solution I should prove that $\Delta_1+\Delta_2\le n-1$ ($\Delta_1$ and $\Delta_2$ are maximal degree of vertices of graphs $G$ and $\overline{G}$). But I think it is not a correct inequality.