Back to search

Rochester Institute of Technology

The Chromatic Villainy of Complete Multipartite Graphs

Abstract

dc:description.abstract

Suppose 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 × 1

Identifiers

dc:identifier.*
Repository record dc:identifier
https://repository.rit.edu/theses/9889

Chain of custody

source
Harvested from
Rochester Institute of Technology
Base URL
repository.rit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Raleigh, Anna. The Chromatic Villainy of Complete Multipartite Graphs. Thesis thesis, https://repository.rit.edu/theses/9889