Electronic Theses and Dissertations

Slow Coloring Cyclic Permutation Graphs

﻿
Metadata FieldValueLanguage
dc.contributor.advisorPuleo, Gregory
dc.contributor.authorMorris, Joan
dc.date.accessioned2021-04-12T19:41:37Z
dc.date.available2021-04-12T19:41:37Z
dc.date.issued2021-04-12
dc.identifier.urihttps://etd.auburn.edu//handle/10415/7632
dc.description.abstractThe slow coloring game is played by two players, Lister and Painter, on a graph $$G$$. In round $$i$$, Lister marks a nonempty subset of $$V(G)$$, which we'll call $$M$$. By doing this he scores $$|M|$$ points. Painter responds by deleting a maximal independent subset of $$M$$. This process continues until all vertices are deleted. Lister aims to maximize the score, while Painter aims to minimize it. The best score that both players can guarantee is called the slow coloring number or sum-color cost of $$G$$, denoted $$\spo{(G)}$$. Puleo and West found that for an $$n$$-vertex tree $$T$$, $$\spo(T) \leq \lfloor \frac{3n}{2} \rfloor$$, and that the maximum is reached when $$T$$ contains a spanning forest with vertices of degree 1 or 3. This implies that graphs with a perfect matching have a slow coloring number bounded by $$\spo(G) \geq \frac{3n}{2}$$. We find a stronger lower bound for cyclic permutation graphs. Given a cyclic permutation graph $$G_\sigma$$, $$\sigma \in S_k$$, we show $$\spo(G_\sigma) \geq \frac{3n}{2} + 1$$.en_US
dc.subjectMathematics and Statisticsen_US
dc.titleSlow Coloring Cyclic Permutation Graphsen_US
dc.typeMaster's Thesisen_US
dc.embargo.statusNOT_EMBARGOEDen_US
dc.embargo.enddate2021-04-12en_US