Online sum-paintability: the slow-coloring game

DOI10.1016/J.DISC.2018.01.001zbMATH Open1380.05131arXiv1507.06513OpenAlexW2964261055MaRDI QIDQ1699554FDOQ1699554

Douglas B. West, Thomas Mahoney, Gregory J. Puleo

Publication date: 23 February 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: The slow-coloring game is played by Lister and Painter on a graph $G$. On each round, Lister marks a nonempty subset $M$ of the uncolored vertices, scoring $|M|$ points. Painter then gives a color to a subset of $M$ that is independent in $G$. The game ends when all vertices are colored. Painter and Lister want to minimize and maximize the total score, respectively. The best score that each player can guarantee is the sum-color cost of $G$, written $mathringmathrms(G)$. The game is an online variant of online sum list coloring. We proe $frac|V(G)|2alpha(G)+frac12leqfracmathringmathrms(G)|V(G)|leqmaxleftfrac|V(H)|alpha(H):HsubsetGight$, where $alpha(G)$ is the independence number, and we study when equality holds in the bounds. We compute $mathringmathrms(G)$ for graphs with $alpha(G)=2$. Among $n$-vertex graphs, we prove that $mathringmathrms$ is minimized by the star and maximized by the path. We also obtain good bounds on $mathringmathrms(K_{r,s})$.

Full work available at URL: https://arxiv.org/abs/1507.06513

zbMATH Keywords

complete bipartite graphHall ratioslow-coloring gamesum choosabilitysum paintability

Mathematics Subject Classification ID

2-person games (91A05) Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• Mr. Paint and Mrs. Correct
• Random graphs.
• Title not available (Why is that?)
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• Cliques in random graphs
• The chromatic number of random graphs
• Sum choice numbers of some graphs
• On-line list colouring of graphs
• Sum list coloring graphs
• Sum list coloring block graphs
• Hall ratio of the Mycielski graphs
• List colorings with distinct list sizes, the case of complete bipartite graphs
• The sum choice number of \(P_3 \square P_n\)
• Sum list coloring \(2\times n\) arrays
• The chromatic sum of a graph: history and recent developments
• Sum-paintability of generalized theta-graphs
• On the ultimate lexicographic Hall-ratio
• The fractional chromatic number, the Hall ratio, and the lexicographic product
• Asymptotic values of the Hall-ratio for graph powers
• Title not available (Why is that?)
• Online sum-paintability: the slow-coloring game

Cited In (7)

• Slow coloring of \(3k\)-connected graphs
• The interactive sum choice number of graphs
• The interactive sum choice number of graphs
• The independence coloring game on graphs
• Online sum-paintability: slow-coloring of trees
• Online sum-paintability: the slow-coloring game
• Indicated domination game

This page was built for publication: Online sum-paintability: the slow-coloring game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1699554)