Chromatic number vs chromatic index

[caffeinemachine]

My friend gave me a question as a challenge. The question is:

Let $G$ be a non-complete simple graph. Prove that $\chi (G) \leq \chi (L(G))$.
Here $L(G)$ is the line graph of $G$ and $\chi (G)$ represents the chromatic number of $G$ and $\chi (L(G))$ is the chromatic number of $L(G)$ a.k.a chromatic index of $G$.

He said that he was able to prove it directly, that is, without using sophisticated theorems like Brook's theorem. (Use of Brook's theorem provides a trivial proof)I've been able to reduce it to the following special case(I will post how I arrived at this if anyone needs it):
Let $G$ be a $k$-regular non-complete simple graph with $\chi (G) = k+1$. Also assume $\chi (G-e) < \chi (G) \, \, \forall e \in E(G)$. Prove that $\chi (G) \leq \chi (L(G))$.

We know by Brook's theorem that the only graphs satisfying the hypothesis of the above mentioned special case are graphs isomorphic to odd cycles. So maybe this thing can be proved without Brook's theorem and we'll be done.
Can anybody see how can I proceed from here?

 

[Sudharaka]

Let $G$ be a non-complete simple graph. Prove that $\chi (G) \leq \chi (L(G))$.

Hi caffeinemachine, :)

I was wondering whether this is a true statement. For example consider the following graph with three vertices out of which two are connected by a single edge. This is a non-complete simple graph. And it's line graph contains only one vertex. Therefore, \(\chi (G)=2\) but \(\chi (L(G))=1\).

Kind Regards,
Sudharaka.

 

[caffeinemachine]

Hi caffeinemachine, :)

I was wondering whether this is a true statement. For example consider the following graph with three vertices out of which two are connected by a single edge. This is a non-complete simple graph. And it's line graph contains only one vertex. Therefore, \(\chi (G)=2\) but \(\chi (L(G))=1\).

Kind Regards,
Sudharaka.

That's right Sudharaka. I think $G$ has to be assumed to be connected. Then by Brook's theorem I can show that the statement is true.

 

[Sudharaka]

That's right Sudharaka. I think $G$ has to be assumed to be connected. Then by Brook's theorem I can show that the statement is true.

Well even if \(G\) is assumed to be connected it seem to be not enough. For example let \(G\) be the graph of two vertices and one edge. This provides a simple counterexample.

 

[caffeinemachine]

Well even if \(G\) is assumed to be connected it seem to be not enough. For example let \(G\) be the graph of two vertices and one edge. This provides a simple counterexample.

But then that graph is isomorphic to $K_2$. The hypothesis of the question excludes complete graphs!

 

[Sudharaka]

But then that graph is isomorphic to $K_2$. The hypothesis of the question excludes complete graphs!

You have mentioned in post #3 that \(G\) needs to be a connected graph after I gave a counterexample in post #2. :)

 

[caffeinemachine]

You have mentioned in post #3 that \(G\) needs to be a connected graph after I gave a counterexample in post #2. :)

Sorry if that caused confusion. I meant for connectedness to be taken as additional hypothesis.

 

[Sudharaka]

Sorry if that caused confusion. I meant for connectedness to be taken as additional hypothesis.

Ah, now I understand it perfectly. I think it was me who confused it. :) Anyway let me rephrase the theorem,

Let \(G\) be a connected, non-complete simple graph. Prove that \(\chi (G) \leq \chi (L(G))\).

Can you please explain what you meant by,

We know by Brook's theorem that the only graphs satisfying the hypothesis of the above mentioned special case are graphs isomorphic to odd cycles. So maybe this thing can be proved without Brook's theorem and we'll be done.

in your original post? The Brook's theorem does not apply for odd cycles, so what I don't get is how you employ the Brook's theorem to predict something related to odd cycles?

Kind Regards,
Sudharaka.

 

[caffeinemachine]

Ah, now I understand it perfectly. I think it was me who confused it. :) Anyway let me rephrase the theorem,
Can you please explain what you meant by,
in your original post? The Brook's theorem does not apply for odd cycles, so what I don't get is how you employ the Brook's theorem to predict something related to odd cycles?

Kind Regards,
Sudharaka.

Let G be connected non-complete simple graph.

Case1:$G$ is a cycle
Here $G$ is isomorphic to $L(G)$. Thus $\chi (G)= \chi (L(G))$

Case2: $G$ is not a cycle.
Invoking Brook's theorem we have $\chi (G) \leq \Delta (G)$. Clearly $L(G)$ contains a clique of size $\Delta (G)$. Thus $\Delta (G) \leq \chi (L(G)) $. And thus we have $\chi (G) \leq \chi (L(G))$.