On Chromatic Number of Graph and Its Complement

We want to prove that $n \leq χ (G) χ (\overset{―}{G}) \leq \frac{(n + 1)^{2}}{4}$ .

I think it is clear that for the upper bound, we want to prove $χ (G) + χ (\overset{―}{G}) \leq n + 1$ instead. The bound above is implied from AM-GM.

Lower Bound

We color each vertex with a pair $(a, b)$ , the color in $G$ and $\overset{―}{G}$ respectively. The total number of such pairs is clearly $χ (G) χ (\overset{―}{G})$ . If we have $χ (G) χ (\overset{―}{G}) < n$ , by pigeon hole we would find two vertices with the same pair of colors. This is a contradiction.

Upper Bound (Proof 1)

This was my proof 2 years ago. It is the ugliest proof out of the 3 given below.

Lemma 1: We can partition $G$ into empty graphs $V_{i}$ with the additional constraint that for all $i < j$ and $v_{1} \in V_{j}$ , there exists some $v_{2} \in V_{i}$ such that $v_{1}$ and $v_{2}$ are connected.

Proof of Lemma 1: We will algorithmically construct this partition. Start with $V_{i}$ being the singleton sets endowed with some arbitrary ordering. If there exists $(i, j, v_{1})$ that does not satisfy the constraint, then we are allowed to delete $v_{1}$ from $V_{j}$ and add it to $V_{i}$ . The new partition will satisfy the property that all components are empty graphs.

Then our algorithm will evantually terminate. Define the potential as the sum of the index of $V_{i}$ where each vertex is contained. Initially our potential is $\frac{n (n + 1)}{2}$ . Each operation will strictly decrease the potential. As for empty sets of $V_{i}$ , just delete them at the end. $◼$

Let there be $k$ components in our above partition into empty graphs. Then we can construct a partition of $G$ into $n - k + 1$ cliques $U_{j}$ , which is a $n - k + 1$ coloring of $\overset{―}{G}$ .

Start with $U_{j}$ being the singleton sets. For each $i = 2$ to $k$ , we will pick an arbitrary vertex $v \in V_{i}$ and then merge it with some other component in $U_{i}$ that is entirely in $V_{1} \cup V_{2} \cup \dots \cup V_{i - 1}$ .

Consider the components of $U_{j}$ inside $V_{1} \cup V_{2} \cup \dots \cup V_{i - 1}$ . It is easy to see that $\sum (∣ U_{j} ∣ - 1) = i - 2$ . Therefore, since $v$ has at least $i - 1$ vertices to $V_{1} \cup V_{2} \cup \dots \cup V_{i - 1}$ (at least one to each component), there exists a component of $U_{j}$ where all the vertices are connected to $v$ . So we merge $v$ with that component.

Upper Bound (Proof 2)

This proof was given in https://www.jstor.org/stable/2306658 in 1956.

We proceed by induction on single vertices.

Suppose our graph has size $n$ . We want to prove that $χ (G) + χ (\overset{―}{G}) \leq n + 1$ .

If $n = 1$ , obviously $χ (G) = χ (\overset{―}{G}) = 1$ .

Otherwise, if $n > 1$ , pick some arbitrary $v \in G$ and consider $H = G - v$ .

Case 1: $χ (H) + χ (\overset{―}{H}) \leq n - 1$ , choose new colors for $v$ in both $G$ and $\overset{―}{G}$ .

Case 2: $χ (H) + χ (\overset{―}{H}) = n$ , notice that we only need to choose a new color for $v$ in $G$ if the degree of $v$ is at least $χ (H)$ in $G$ . Ditto for $\overset{―}{G}$ and $χ (\overset{―}{H})$ . But, the total degree of $v$ in $G$ and $\overset{―}{G}$ is $n - 1$ . The degree of $v$ cannot be both at least $χ (H)$ and $χ (\overset{―}{H})$ in both $G$ and $\overset{―}{G}$ respectively. So we only need to choose a new color for $v$ in one of $G$ or $\overset{―}{G}$ .

Upper Bound (Proof 3)

This proof was given by Anton Trygub. I think it is the best proof.

Lemma 2: If $χ (G) \geq c$ , then we can find an induced subgraph $H \subseteq G$ such that $min \deg (H) \geq c - 1$ .

Proof of Lemma 2: We will prove the contrapositive. Suppose for all induced subgraphs $H \subseteq G$ , we can find a vertex that such that $min \deg (H) < c - 1$ . Then we can produce an ordering $v_{1}, v_{2}, \dots, v_{n}$ of the vertices of $G$ such that $v_{i}$ has at most $c - 2$ edges in $v_{1}, v_{2}, \dots, v_{i - 1}$ . The construction is to go from $i = n$ to $1$ and set $v_{i}$ as the vertex with minimum degree and delete it from $G$ . A greedy coloring of vertices from $i = 1$ to $n$ gives us the desired $(c - 1)$ -coloring. $◼$

Now, suppose that there is a certificate for the fact that $χ (G) \geq k + 1$ and $χ (\overset{―}{G}) \geq n - k + 1$ for some $k$ . The graph $H_{1} \subseteq G$ with $min \deg_{G} (H_{1}) \geq k$ has at least size $k + 1$ . Similarly, the graph $H_{2} \subseteq \overset{―}{G}$ with $min \deg_{\overset{―}{G}} (H_{2}) \geq n - k$ has at least size $n - k + 1$ .

Therefore, there is a vertex $v$ that is in $H_{1} \cap H_{2}$ . This vertex has degree at least $k$ in $G$ and degree at least $n - k$ in $\overset{―}{G}$ . So the total degree of $v$ is at least $n$ . Contradiction.

Now, it seems as though this proof is non-constructive but we can easily make it constructive. For $G$ and $\overset{―}{G}$ we will run our algorithm in lemma 2 to find a greedy coloring by repeatedly deleting the vertex with the minimum degree. Then we have just proved that if this strategy produces a coloring that uses too many colors, we have a contradiction.

Mala Chicken McCrispy

The Devil’s Algorithm