English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The \emph{slow-coloring game} is played by Lister and Painter on a graph $G$.Initially, all vertices of $G$ are uncolored. In each round, Lister marks anonempty set $M$ of uncolored vertices, and Painter colors a subset of $M$ thatis independent in $G$. The game ends when all vertices are colored. The scoreof the game is the sum of the sizes of all sets marked by Lister. The goal ofPainter is to minimize the score, while Lister tries to maximize it. We providestrategies for Painter on various classes of graphs whose vertices can bepartitioned into a bounded number of sets inducing forests, including$k$-degenerate, acyclically $k$-colorable, planar, and outerplanar graphs. Forexample, we show that on an $n$-vertex graph $G$, Painter can keep the score toat most $\frac{3k+4}4n$ when $G$ is $k$-degenerate, $3.9857n$ when $G$ isacyclically $5$-colorable, $3n$ when $G$ is planar with a Hamiltonian dual,$\frac{8n+3m}5$ when $G$ is $4$-colorable with $m$ edges (hence $3.4n$ when $G$is planar), and $\frac73n$ when $G$ is outerplanar.

The Slow-coloring Game on Sparse Graphs: $k$-Degenerate, Planar, and Outerplanar