The Slow-Coloring Game on Path Power Graphs
Metadata Field | Value | Language |
---|---|---|
dc.contributor.advisor | Johnson, Peter | |
dc.contributor.author | Graves, Josey | |
dc.date.accessioned | 2022-11-16T17:20:09Z | |
dc.date.available | 2022-11-16T17:20:09Z | |
dc.date.issued | 2022-11-16 | |
dc.identifier.uri | https://etd.auburn.edu//handle/10415/8443 | |
dc.description.abstract | The Slow-Coloring Game is a game played on a graph G by two players which we will refer to as Lister and Painter. In the ith round, Lister marks a nonempty subset M of V (G) of uncolored vertices as eligible to receive color i, scoring |M| points. Painter then gives color i to a subset of M that is independent in G. The game ends when all of the vertices of G are colored. Note that at each stage the resulting coloring will be a proper coloring of V(G). Lister’s goal is to maximize the total score while Painter seeks to minimize the total score. The sum-color cost of a graph G, denoted s(G), is the best score each player can guarantee in the Slow-Coloring Game on G regardless of the play strategy of the other. Puleo and West gave upper and bounds for the sum-color cost for every tree T on n vertices. They also conjectured that this bound generalizes to k-trees. Mahoney, Puleo, and West provide the value for the sum-color cost of k-stars, we provide the value for the sum-color cost of k-paths. | en_US |
dc.subject | Mathematics and Statistics | en_US |
dc.title | The Slow-Coloring Game on Path Power Graphs | en_US |
dc.type | Master's Thesis | en_US |
dc.embargo.status | NOT_EMBARGOED | en_US |
dc.embargo.enddate | 2022-11-16 | en_US |
dc.contributor.committee | McDonald, Jessica | |
dc.contributor.committee | Briggs, Joseph |