# Graph Coloring and Complete Graph

If a graph is k-colorable, then does it imply that it must have a k-complete graph as it's subgraph? For example if a graph has chromatic no = 5, then is this sufficient to imply that it must have K5 as its subgraph?

Basically I am trying to solve this question of MIT 6.042, problem set 4 (2010):

Let ($s_1$, $s_2$, ..., $s_n$) be an arbitrarily distributed sequence of the number 1, 2, ..., n − 1, n. For instance, for n = 5, one arbitrary sequence could be (5, 3, 4, 2, 1).

Define the graph G=(V,E) as follows:

1. V = {v1, v2, ..., vn}
2. e = (vi, vj ) ∈ E if either:

a. j = i + 1, for 1 ≤ i ≤ n − 1

b. i = $s_k$, and j = $s_{k+1}$ for 1 ≤ k ≤ n−1

Prove that this graph is 4-colorable for any (s1, s2, ..., sn).

Hint: First show that that a line graph is 2-colorable. Note that a line graph is defined as follows: The n-node graph containing n-1 edges in sequence is known as the line graph $L_n$

My approach: Trying to prove by contradiction, I will assume that graph G is not 4-colorable, then it requires atleast 5 colours, this implies that there must be K-5 as a subgraph in G (Now here I am using a strong statement about which I am not sure). Then I will show that K-5 is not possible under the definitions of graph G, hence a contradiction. Is this approach correct or is there a better one?

• Any odd cycle graph has chromatic number $3$, but usually not $K_3$ as subgraph. – Hagen von Eitzen Apr 13 '15 at 10:14
• except for k=3 case, any idea? – Pranav Bisht Apr 13 '15 at 10:32
• For all $k$, there are graphs of chromatic number $k$ that do not have a complete subgraph with $k$ vertices. In fact, there are even graphs of chromatic number $k$ without any cycles of length smaller than $\ell$, for any given $\ell$! – Casteels Apr 13 '15 at 14:05
• Any suggestions on solving the question? – Pranav Bisht Apr 13 '15 at 14:09
• Your part (a) condition for the edges seems incomplete – Casteels Apr 13 '15 at 14:15

I have been working on this same problem and found this older question on this forum.

Here is the link to the pdf for the problem set:

Problem Set 4

This is question 6 (a). Here is how I think you are supposed to answer it.

First you color the vertices 1 through n with 2 colors, say blue and red, just using the first set of edges like $(v_i,v_j)$ where j=i+1, 1<=i<=n-1

So now the graph from vertex 1 to vertex n looks like this:

R-B-R-B-....

Now you have to add the edges $(v_{S_k},v_{S_k+1})$, 1<=k<=n-1, one at a time adjusting the color of $v_{S_k+1}$ so it is different from the color of the vertices that it is connected to.

But there are only three possible vertices connected to the new vertex $v_{S_k+1}$. There are at most two from the original line and then also $v_{S_k}$. The two from the original line would be labeled $v_{(S_k+1)-1}$ and $v_{(S_k+1)+1}$.

So, as you add each edge $(v_{S_k},v_{S_k+1})$ you just have to pick at most a fourth color to color $v_{S_k+1}$, a different color from $v_{S_k}$, $v_{(S_k+1)-1}$ and $v_{(S_k+1)+1}$.