Slow Coloring Cyclic Permutation Graphs

Abstract

The 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\).