Date of Award

2020

Document Type

Thesis

Degree Name

Bachelor of Science

Department

Mathematics

First Advisor

Dr. Prateek Bhakta

Abstract

Graphs are a well studied construction in discrete math, with one of the most common areas of study being graph coloring. The graph coloring problem asks for a color to be assigned to each vertex in a graph such that no two adjacent vertices share a color. An assignment of k colors that meets these criteria is called a k-coloring. The coloring graph Ck(G) is defined as the graph where every vertex represents a valid k-coloring of graph G and edges exist between colorings that di↵er by one vertex. We call graph G the base graph of the k-coloring graph Ck(G). A primary point of interest in coloring graph research is that of connectivity, and specifically, biconnectivity. To assist this research, we wrote software to compute and display coloring graphs. The software package allows the user to construct base graphs in a GUI. After construction, a fast backtracking algorithm with bit-arithmetic is used to compute all possible colorings of the base graph. To aid understanding of biconnectivity, we use an enhanced version of Robert Tarjan’s cut-vertex algorithm to identify biconnected components in the coloring graph and build a block-cut tree, or metagraph. The software has been useful in coloring graph research, especially for finding counter examples to hypotheses since base graphs can be randomly generated in mass numbers.

Download

Share

COinS