Page 248 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 248
ALGORITHMIC GRAPH THEORY (MS-54)
The Slow-Coloring Game on a Graph
Douglas West, dwest@illinois.edu
Zhejiang Normal University, China, and University of Illinois, United States
The 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 a non-empty set M of uncolored vertices, and
Painter colors a subset of M that is independent in G. The game ends when all vertices are
colored. The score of the game is the sum of the sizes of all sets marked by Lister. The goal of
Painter is to minimize the score, while Lister tries to maximize it; the score under optimal play
is the cost of the graph.
A greedy strategy for Painter keeps the cost of G to at most χ(G)n when G has n vertices,
which is asyptotically sharp for Turán graphs. On various classes Painter can do better. For n-
vertex trees the maximum cost is 3n/2 . There is a linear-time algorithm and inductive formula
to compute the cost on trees, and we know all the extremal n-vertex trees. Also, Painter can
keep the cost to at most (1 + 3k/4)n when G is k-degenerate, 7n/3 when G is outerplanar,
3.9857n when G is acyclically 5-colorable, and 3.4n when G is planar. These bounds are not
believed to be sharp.
We will discuss strategies (algorithms) for Lister and Painter that establish various lower and
upper bounds. The results appear in three papers with various subsets of Grzegorz Gutowski,
Tomasz Krawczyk, Thomas Mahoney, Krzysztof Maziarz, Gregory J. Puleo, Michal Zajac, and
Xuding Zhu.
Approximate and Randomized algorithms for Computing a Second
Hamiltonian Cycle
Viktor Zamaraev, Viktor.Zamaraev@liverpool.ac.uk
University of Liverpool, United Kingdom
In 1946 Cedric Smith proved, using a non-constructive parity argument, that any cubic Hamil-
tonian graph contains at least two Hamiltonian cycles.
This motivated the following computational problem, which is still largely open: given a
Hamiltonian cycle C in a cubic Hamiltonian graph G, can we efficiently compute a second
Hamiltonian cycle?
In this talk, I will discuss various open questions surrounding this problem and present some
efficient approximate and randomized algorithms for related problems.
Joint work with Argyrios Deligkas, George B. Mertzios, and Paul G. Spirakis
246
The Slow-Coloring Game on a Graph
Douglas West, dwest@illinois.edu
Zhejiang Normal University, China, and University of Illinois, United States
The 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 a non-empty set M of uncolored vertices, and
Painter colors a subset of M that is independent in G. The game ends when all vertices are
colored. The score of the game is the sum of the sizes of all sets marked by Lister. The goal of
Painter is to minimize the score, while Lister tries to maximize it; the score under optimal play
is the cost of the graph.
A greedy strategy for Painter keeps the cost of G to at most χ(G)n when G has n vertices,
which is asyptotically sharp for Turán graphs. On various classes Painter can do better. For n-
vertex trees the maximum cost is 3n/2 . There is a linear-time algorithm and inductive formula
to compute the cost on trees, and we know all the extremal n-vertex trees. Also, Painter can
keep the cost to at most (1 + 3k/4)n when G is k-degenerate, 7n/3 when G is outerplanar,
3.9857n when G is acyclically 5-colorable, and 3.4n when G is planar. These bounds are not
believed to be sharp.
We will discuss strategies (algorithms) for Lister and Painter that establish various lower and
upper bounds. The results appear in three papers with various subsets of Grzegorz Gutowski,
Tomasz Krawczyk, Thomas Mahoney, Krzysztof Maziarz, Gregory J. Puleo, Michal Zajac, and
Xuding Zhu.
Approximate and Randomized algorithms for Computing a Second
Hamiltonian Cycle
Viktor Zamaraev, Viktor.Zamaraev@liverpool.ac.uk
University of Liverpool, United Kingdom
In 1946 Cedric Smith proved, using a non-constructive parity argument, that any cubic Hamil-
tonian graph contains at least two Hamiltonian cycles.
This motivated the following computational problem, which is still largely open: given a
Hamiltonian cycle C in a cubic Hamiltonian graph G, can we efficiently compute a second
Hamiltonian cycle?
In this talk, I will discuss various open questions surrounding this problem and present some
efficient approximate and randomized algorithms for related problems.
Joint work with Argyrios Deligkas, George B. Mertzios, and Paul G. Spirakis
246
