Title: A Heuristic for Improving Given Graph Colorings
Student: Grant Smith gcs37@txstate.edu
Advisor: Martin Burtscher
Date and Time: Wed Dec 7 2022 1:00 PM CST
Location: https://txstate.zoom.us/my/martin.burtscher
Abstract:
Graph coloring is the process of assigning a label to each vertex of a graph such that no two adjacent vertices have the same label and as few distinct labels as possible are used. It is an important step in many computations, including register allocation in compilers and logistics distribution. Since graph coloring is NP-hard, heuristics are used in practice that produce a valid coloring but may need more colors (i.e., labels) than the optimal solution. I present an algorithm that tries to improve the colorings produced by such heuristics. A vertex's color can often be changed after recursively changing the colors of some strategically chosen adjacent vertices. Applying this idea to all vertices of a particular color may eliminate that color from the graph, thus reducing the total number of colors needed. This algorithm yields an improvement on many graphs and can improve the solutions of the currently best heuristics by up to four colors.
Deadline: Dec. 30, 2022, midnight