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
    $\begingroup$ This question would be greatly improved by defining “class 1” and $\Delta(G)$ $\endgroup$ – Stella Biderman Jan 14 '18 at 12:42
  • $\begingroup$ @StellaBiderman done $\endgroup$ – mandella Jan 14 '18 at 12:57
  • $\begingroup$ Do you use the definition of coloring where a graph is $m$-colorable if there is a way to assign $m$ colors legally, or do you also require that $m$ be minimal. That’s is, would you say that $C_6$ is both $2$ colorable and $6$ colorable, or just $2$ colorable? $\endgroup$ – Stella Biderman Jan 14 '18 at 13:05
  • $\begingroup$ @StellaBiderman no I want the least $m$. So $C_6$ would be 2-colorable. $\endgroup$ – mandella Jan 14 '18 at 13:07
  • 3
    $\begingroup$ Take the complete 4 graph. Remove an edge. This has maximum degree 3, it is 3 colorable, but is not bipartite $\endgroup$ – Exodd Jan 14 '18 at 13:57

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.

  • $\begingroup$ Yes! Thank you. I could not find a counterexample :) $\endgroup$ – mandella Jan 15 '18 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.