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?

  • $\begingroup$ Any odd cycle graph has chromatic number $3$, but usually not $K_3$ as subgraph. $\endgroup$ – Hagen von Eitzen Apr 13 '15 at 10:14
  • $\begingroup$ except for k=3 case, any idea? $\endgroup$ – Pranav Bisht Apr 13 '15 at 10:32
  • $\begingroup$ 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$! $\endgroup$ – Casteels Apr 13 '15 at 14:05
  • $\begingroup$ Any suggestions on solving the question? $\endgroup$ – Pranav Bisht Apr 13 '15 at 14:09
  • $\begingroup$ Your part (a) condition for the edges seems incomplete $\endgroup$ – 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:


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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.