The goal of graph edge coloring is to color a graph G with as few colors as possible such that each edge receives a color and that adjacent edges, that is, different edges incident to a common vertex, receive different colors. The chromatic index, denoted χ′(G), is the minimum number of colors required for such a coloring to be possible. There are two important lower bounds for χ′(G) on every graph: maximum degree, denoted ∆(G), and density, denoted ω(G). Combining these two lower bounds, we know that every graph’s chromatic index must be at least ∆(G) or ω(G), whichever is greater. In this paper, we prove that the chromatic index of every ring graph is exactly equal to this lower bound.
Dr. Guantao Chen
"The Chromatic Index of Ring Graphs,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 23:
2, Article 6.
Available at: https://scholar.rose-hulman.edu/rhumj/vol23/iss2/6