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

720 Views Asked by At

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?

1

There are 1 best solutions below

1
On BEST ANSWER

It is a theorem of König that all bipartite graphs $G$ are $\Delta(G)$-edge-colorable. See this math stackexchange thread Edge-coloring of bipartite graphs.

It is not true that all $\Delta(G)$-edge-colorable graphs are bipartite. Take $K_4$, which is not bipartite but is $3$-edge-colorable.