Online sum-paintability: the slow-coloring game

DOI10.1016/J.DISC.2018.01.001MaRDI QIDQ1699554zbMATHOpenAlexFDO

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

Publication date 23 February 2018

Published in Discrete Mathematics (Search for Journal in Brave)

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)

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})$.

Recommendations

• Online sum-paintability: slow-coloring of trees
• The slow-coloring game on sparse graphs: \(k\)-degenerate, planar, and outerplanar
• An infinite family of sum-paint critical graphs
• Families of online sum-choice-greedy graphs
• Sum-paintability of generalized theta-graphs

Cites work

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

Cited in

(9)

• The slow-coloring game on sparse graphs: \(k\)-degenerate, planar, and outerplanar
• Slow coloring of \(3k\)-connected graphs
• Online sum-paintability: slow-coloring of trees
• Online sum-paintability: the slow-coloring game
• An infinite family of sum-paint critical graphs
• The interactive sum choice number of graphs
• The interactive sum choice number of graphs
• Indicated domination game
• The independence coloring game on graphs

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)