2023/04/03 by Joan K. Morris, Morris, Joan, Gregory J. Puleo +1
Computer Science · Decision Sciences · Mathematics · #05C15(Primary) #05C57 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Game Theory and Applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2304.01368
openalex publication_date 2023/04/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The slow coloring game was introduced by Mahoney, Puleo, and West and it is played by two players, Lister and Painter, on a graph \(G\). In round \(i\), Lister marks a nonempty subset \(M\) of \(V(G)\). 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\), the slow coloring number is at most \(\lfloor (3n)/(2) \rfloor\), and that the maximum can be reached when \(T\) contains a spanning forest with vertices of degree 1 or 3. This implies that every n-vertex graph \(G\) having a perfect matching satisfies \(\spo(G) ≥ \lfloor(3n)/(2)\rfloor\). In this paper, we prove that for \(3k\)-connected graphs with \(|V(G)| ≥ 4k\) and with a perfect matching the lower bound is higher: \(\spo(G) ≥ (3n)/(2) + k\).