Problem in Chromatic Number

Question

The smallest number of colors needed to color a graph G is called its chromatic number, and is often denoted χ(G).
lemma : If G has a degree sequence $ (d_1, d_2, ... , d_v) $ with $ d_1 \ge d_2 \ge ... \ge d_v $ then $$ \chi \le max_i \; min\{d_i + 1 , i\}. $$ main question : Using lemma, Show that :
a) $ \; \chi \le \lceil\sqrt{2E}\rceil $
b) $ \; \chi(G) + \chi(G^c) \le V + 1$

Answer 1

The lemma is true (it reflects the greedy coloring algorithm), but the first statement is false: let $G$ be $K_5$, then $\chi(G)=5$, and $G$ has 10 edges. Now $\chi\leq\sqrt{2E}$ $\iff$ $5\leq\sqrt{20}$ and the last inequality is not true.

For the second statement, let $j$ be the lowest index that maximizes $min(d_i+1,i)$, let $a=min(d_j+1,j)$, so $a\leq j$ and $a\leq d_j+1$.

Let $n$ be the number of vertices of $G$.

$G^c$ has degree sequence $n-1-d_n\geq\ldots\geq n-1-d_1$, so the $i$th element of the degree sequence is $n-1-d_{n-i+1}$. Let $k$ be the lowest index that maximizes $min(n-1+d_{n-i+1}+1,i)$, let $b=min(n-d_{n-k+1},k)$, so $b\leq k$ and $b\leq n-d_{n-k+1}$.

Let $\chi=\chi(G)$ and $\chi'=\chi(G^c)$. The lemma tells us the $\chi\leq a$ and $\chi'\leq b$.

Case 1: $j+k\leq n+1$, then $\chi+\chi'\leq a+b\leq j+k\leq n+1$.

Case 2: $j+k>n+1$, then $j>n+1-k$, so $d_j\leq d_{n+1-k}$. Now $\chi+\chi'\leq a+b\leq d_j+1+n-d_{n-k+1}\leq n+1$.

Solution for modified first problem.

Again let $j$ be the first index that realizes the maximum, so again $\chi\leq j$ and $\chi\leq d_j+1$. Then $2E=\sum d_i\geq d_1+\ldots+d_j\geq jd_j\geq\chi(\chi-1)$. But then $\chi=\lceil\sqrt{\chi(\chi-1)}\rceil\leq\sqrt{2E}$.