Minimum clique cover relationship with Chromatic number For a general graph, can we say that the summation of minimum clique cover and chromatic number is upper bound by n+1 where n is the total number of vertices in the graph? If not, what is the relationship. Note that I am not talking about complement graph.
 A: Yes, it is true.  The sum of the chromatic number $\chi(G)$ of the graph and the minimum size of a partition of the vertex set into cliques is at most $n+1$, where $n$ is the number of vertices. Observe that partitioning the vertex set of $G$ into cliques is equivalent to partitioning the vertex set of the complement graph $\overline{G}$ into independent sets.  So the second term in the sum is the chromatic number $\chi(\overline{G})$. 
To prove that $\chi(G) + \chi(\overline{G} \le n+1$, order the vertices $x_i$ so that $d(x_1) \ge d(x_2) \ge \cdots \ge d(x_n)$.  Do a greedy coloring of the vertices of $G$ in order $x_1,\ldots,x_n$, and a greedy coloring of $\overline{G}$ in order $x_n, \ldots, x_1$. It can be shown that the total number of colors used in both these colorings is at most $n+1$. 
A: Notwithstanding your weird remark that you're "not talking about complement graph", the clique cover number of a graph $G$ (the minimum number of cliques needed to cover the vertices) is obviously equal to $\chi(\overline G),$ the chromatic number of the complementary graph $\overline G;$ see the answer to this question. So the statement you want to prove is obviously equivalent to the following:

For any graph $G$ with $n$ vertices, $\chi(G)+\chi(\overline G)\le n+1.$

Here is a straightforward proof by induction on $n.$ The statement is obviously true for $n=1.$ Consider any fixed positive integer $n$ and assume that the statement is true for all $n$-vertex graphs; I have to show that it's true for any graph on $n+1$ vertices.
Let $G$ be any (simple) graph with $n+1$ vertices; I have to show that $\chi(G)+\chi(\overline G)\le n+2.$ Choose a vertex $v$ of $G.$ By the inductive hypothesis,
$$\chi(G-v)+\chi(\overline G-v)=\chi(G-v)+\chi(\overline{G-v})\le n+1.$$
Since
$$\operatorname{deg}_G(v)+\operatorname{deg}_{\overline G}(v)=n,$$
we must have
$$\operatorname{deg}_G(v)\lt\chi(G-v)\ \text{ or }\ \operatorname{deg}_{\overline G}(v)\le\chi(\overline G-v).$$
Without loss of generality assume that
$$\operatorname{deg}_G(v)\lt\chi(G-v).$$
Then
$$\chi(G)=\chi(G-v)\ \text{ and }\ \chi(\overline G)\le\chi(\overline G-v)+1,$$
whence
$$\chi(G)+\chi(\overline G)\le\chi(G-v)+\chi(\overline G-v)+1\le n+2.$$
