Is it true that if a graph is bipartite iff it is class 1 (edge-coloring)?

by mandella   Last Updated January 14, 2018 13:20 PM

A graph is class 1 if its edge set can be colored with $\Delta(G)$ colors, where $\Delta(G)$ is the maximum degree over all vertices in G. A graph is class 2 if we need $\Delta(G)+1$ colors to color the edge set. I think that if a graph is bipartite then we can color its edges with $\Delta(G)$ colors, while when it is not bipartite this cannot be done.

Is there any counterexample for this? Or is it true?



Related Questions



Different colorings of bipartite graph

Updated September 14, 2017 10:20 AM

$χ(G) = 2$ if and only if $χ_f (G) = 2$.

Updated March 03, 2017 16:20 PM

k2,2 with the same colour for every coloring of k3,7

Updated October 20, 2017 22:20 PM