Question

Let G be a graph on n vertices and G' be the complement of G. Give an argument supporting why the chromatic number of G times the chromatic number of G' is greater than or equal to n.

Answer 1

Сhromatic number $\chi(G)$ of a graph G is the smallest number of colors needed to color vertices of G so that every two vertices connected by an edge in G have different colors (we name such colorings as valid colorings).

Let $\chi(G)=k, \chi(G’)=m, I_k=\{1,2,\dots, k\}, I_m=\{1,2, \dots,m\}$ .

Let $\phi: V(G)\to I_k, \psi: V(G)\to I_m$ are valid colorings of G and G’.

Then $(\phi,\psi): V(G)\to I_k\times I_m$ is a valid coloring of the full graph $G\cup G’$ .

Indeed, let $v_1$ and $v_2$ be two vertices of G.

Then they are connected by the edge $(v_1, v_2)$ either in G or in G’.

If $(v_1, v_2)\in E(G)$ then $(\phi(v_1),\psi(v_1))\ne (\phi(v_2),\psi(v_2))$ as $\phi(v_1)\ne \phi(v_2)$.

If $(v_1, v_2)\in E(G’)$ then $(\phi(v_1),\psi(v_1))\ne (\phi(v_2),\psi(v_2))$ as $\psi(v_1)\ne \psi(v_2)$ .

As we have a valid coloring of the full graph $G\cup G’$, the number of used colors must be greater or equal than $χ(G\cup G’)$. But $\chi(G\cup G’)=n$ , as all n vertices of this graph are connected. On the other hand, we used not greater than $km$ colors for a valid coloring of this graph.

Therefore, $km\geq n$ , as required.