•  
  •  
 

Abstract

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.

Author Bio

Lilian Shaffer is an undergraduate student at Georgia State University in Atlanta, Georgia. She joined the RIMMES program, GSU’s undergraduate mathematics research program, during the Fall 2021 semester. Over the course of the Fall 2021 and Spring 2022 semesters, she worked with her mentor, Dr. Guantao Chen, to make progress on the graph edge coloring problem. While she is pursuing a bachelor’s degree in mathematics, she is also pursuing minors in English and philosophy. In her free time, she enjoys games and puzzles of all sorts, with a preference for chess.

Download

Share

COinS