- Thread starter
- #1

- Mar 10, 2012

- 834

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?