Rochester Institute of Technology
The Chromatic Villainy of Complete Multipartite Graphs
Abstract
dc:description.abstractSuppose the colors in a $\chi(G)$-coloring of a graph $G$ have been rearranged. We will call this rearrangement c*. The chromatic villainy of the c* is defined as the minimum number of vertices that need to be recolored in order to return c* to a proper coloring in which each color appears the same number of times as in the initial coloring. The maximum chromatic villainy when considering all rearrangements of all $\chi(G)$-coloring of $G$ is the chromatic villainy of $G$. Here, the chromatic villainies of certain families of graphs were investigated and the chromatic villainies of paths and certain classes of complete multipartite graphs were found. Bounds were found for certain classes of odd cycles and complete multipartite graphs as well.
Degree
thesis:*- Name thesis:degree_name
- Applied and Computational Mathematics (MS)
- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- School of Mathematical Sciences (COS)
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Raleigh, Anna
- Contributors dc:contributor
-
- Paul Wenger
Subjects
dc:subject × 1Identifiers
dc:identifier.*- Repository record dc:identifier
- https://repository.rit.edu/theses/9889