My task is to check the least number of colors used in graph coloring which is simply chromatic number of graph. My undirected graph is 2-regular (each vertex is 2-degree). I found solution that
(maximum independent set number)/number of vertices = number of colors (chromatic number)
https://i.sstatic.net/V00wK.jpg - how it looks like
As you see, it can be 2-colored if result is 2 or 3-colored if the result is more than 2.
But I have no idea how I could find an maximum independent set in such graph.
A 2-regular graph is nothing more than a union of disjoint cycles. If any of the cycles have odd length then the chromatic number is 3, otherwise it's 2. It's that simple. You don't need an algorithm for this.
