Prove or dis-prove that it always holds or not $\lambda(G) \leq \chi(G) $

64 Views Asked by At

I want to prove that this inequality holds or not? The inequality is $\lambda(G) \leq \chi(G) $ where $\lambda(G)$ is the minimum number of edges whose deletion from a graph $G$ disconnects $G$, also called the line connectivity and $\chi(G)$ is the chromatic number of graph.

I would be greatly thankful if somebody will tell the answer that how to prove or disprove this inequality?

Thanks alot!

2

There are 2 best solutions below

0
On BEST ANSWER

Here is an example to disaprove the inequality. For a complete bipartite graph $K_{3,4}$, $\lambda (K_{3,4})=3$ and $\chi (K_{3,4})=2$.

6
On

If $\lambda$ denotes the edge connectivity, then what is $$\lambda(K_{m,n}) , \chi(K_{m,n})?$$