Originator: Douglas West (presented by Douglas West - REGS 2011)
Definitions: Two players, Max and Min, together produce a matching in a graph $G$ by alternately choosing an edge to add to it. The game ends when the chosen edges form a maximal matching. Max wants the final matching to be large; Min wants it to be small. Max plays first. The game matching number $\alpha'_{g}(G)$ is the size of the final matching under optimal play by both players. For the variant in which Min plays first, we write the size of the final matching under optimal play as $\hat\alpha'_{g}(G)$.
Background: Game matching number follows in the same spirit as game chromatic number, game domination number, etc., in which players with opposite objectives for the final value together make choices that produce a feasible solution to some optimization problem. The general area can be called competitive optimization. Because the final product is a feasible solution, the value of the game parameter is bounded (in the appropriate direction) by the original optimization parameter. In particular, always $\alpha'_{g}(G)\le\alpha'(G)$ (similarly for $\hat\alpha'_{g}(G)$). From below, since the final matching is a maximal matching, always $\alpha'_{g}(G)≥\alpha'(G)/2$.
One can also play the analogous games with independent sets to define the game independence number of a graph. This is a more general problem, since the game matching number of a graph is just the game independence number of its line graph. For a different sort of generalization, see Game saturation number.
Results: Several of the natural initial questions have been solved by REGS participants. On any graph $G$, the difference between $\alpha'_{g}(G)$ and $\hat\alpha'_{g}(G)$ is at most 1, and either parameter may be larger than the other. Since the difference between the parameters is so small, we limit our attention to $\alpha'_{g}(G)$.
The trivial lower bound on $\alpha'_{g}(G)$ in terms of $\alpha'(G)$ can be improved to (2/3)$\alpha'(G)$, with equality for a disjoint union of 6-cycles. At the cost of an additive constant, one can take the join of $rC_{6}$ with $k$ isolated vertices to increase the minimum degree and connectivity.
Question 1: Which are the graphs $G$ such that $\alpha'_{g}(G)=\alpha'(G)$? What lower bound can be placed on $\alpha'_g(G)$ when $G$ has $n$ vertices and the minimum degree or connectivity is at least $cn$, where $c$ is a constant?
Comments: Equality of course holds for graphs in which every maximal matching is a maximum matching, such as $K_{n}$, $K_{n,n}$, and the tree obtained by singly subdivided each edge of a star. Equality also holds (that is, Max can force a perfect matching) in the cartesian product of any graph with $K_{2}$. A ``copycat'' strategy makes that easy to prove, but the result generalizes. A consequence of the generalization is that Max can force a perfect matching in the cartesian product of any graph with $K_{r,r}$. The generalization proved by the REGS students is that Max can force a perfect matching on any graph $G$ having a perfect matching $M$ such that if $uv,wx∈M$, then $uw∈M$ implies $vx∈M$.
Question 2: As a function of $n$, what is the smallest value of the minimum degree (or edge-connectivity or connectivity) in an $n$-vertex graph needed to force $\alpha'_{g}(G)=\lfloor n/2\rfloor$?
Question 3: What is the smallest value of $\alpha'_{g}(G)$ among $n$-vertex 3-regular graphs? How does the answer change when restricted to $n$-vertex $k$-connected 3-regular graphs, for $k∈${1,2,3}?
Comments: When playing on a path or cycle, optimal play leaves about 1/7 of the vertices unmatched. For trees in general, the REGS students have proved that Max can always force a matching with size at least 3/4 of the matching number, with equality for ``combs'' whose number of vertices is divisible by 8.
Question 4: By the Four Color Theorem, every planar graph has an independent set containing at least 1/4 of its vertices. What is the highest fraction of the vertices that can be guaranteed by Max when playing the independence game on planar graphs?
References:
[Many REGS authors], Game matching number, in preparation.