Lesson 5

Let's start with simple observations. If \(G\) is a tree with at least one edge, then \(\chi(G)=2\): indeed, at least two colors are needed, and they suffice because we can root the tree and color odd levels one color and even levels the other. Also, if \(G\) is a cycle on \(n\) vertices, then \(\chi(G)=2+[n \bmod 2 = 1]\).

It is easy to see that \[\chi(G) \ge \omega(G) \ .\] Indeed, to color a \(k\)-clique, at least \(k\) colors are needed. Also \[\chi(G) \ge \frac{|V|}{\alpha(G)}\ ,\] because in a proper coloring, vertices of one color form an independent set.