2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Probably by chromatic number you mean the least number of colors that suffice to assign vertices colors so that no two adjacent vertices have the same color, although some authors use similar terminology about edge colorings. However a minimum clique cover is a clique cover, not a number per se. Likely you meant the clique cover number(?) so that we would take the "summation" of two integers. I think you should try to fill in some details of your Question, esp. your thoughts on why it might be true (or difficulty you had). $\endgroup$ – hardmath Apr 28 '17 at 2:34
  • $\begingroup$ Why do you say that you are not talking about complement graph? Are you saying that, in your belief, the minimum clique cover number of a graph is NOT the same as the chromatic number of the complementary graph? $\endgroup$ – bof Apr 28 '17 at 2:38
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.