Welcome to our community

Be a part of something great, join today!

chromatic number vs chromatic index

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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

Well-known member
MHB Math Helper
Feb 5, 2012
1,621
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

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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

Well-known member
MHB Math Helper
Feb 5, 2012
1,621
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-known member
MHB Math Scholar
Mar 10, 2012
834
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

Well-known member
MHB Math Helper
Feb 5, 2012
1,621
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

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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

Well-known member
MHB Math Helper
Feb 5, 2012
1,621
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,

caffeinemachine said:
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

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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))$.