Thresholds for the monochromatic clique transversal game

Abstract: We study a recently introduced two-person combinatorial game, the

(a, b)

-monochromatic clique transversal game which is played by Alice and Bob on a graph

G

. As we observe, this game is equivalent to the

(b, a)

-biased Maker-Breaker game played on the clique-hypergraph of

G

. Our main results concern the threshold bias

a_{1} (G)

that is the smallest integer

a

such that Alice can win in the

(a, 1)

-monochromatic clique transversal game on

G

if she is the first to play. Among other results, we determine the possible values of

a_{1} (G)

for the disjoint union of graphs, prove a formula for

a_{1} (G)

if

G

is triangle-free, and obtain the exact values of

a_{1} (C_{n}, s q u a r e, C_{m})

,

a_{1} (C_{n}, s q u a r e, P_{m})

, and

a_{1} (P_{n}, s q u a r e, P_{m})

for all possible pairs

(n, m)

.

This page was built for publication: Thresholds for the monochromatic clique transversal game