  Cram, Domineering, and Arc Kayles are well-studied combinatorial games. They
are interpreted as edge-selecting-type games on graphs, and the selected edges
during a game form a matching. In this paper, we define a generalized game
called Colored Arc Kayles, which includes these games. Colored Arc Kayles is
played on a graph whose edges are colored in black, white, or gray, and black
(resp., white) edges can be selected only by the black (resp., white) player,
although gray edges can be selected by both black and white players. We first
observe that the winner determination for Colored Arc Kayles can be done in
$O^*(2^n)$ time by a simple algorithm, where $n$ is the order of a graph. We
then focus on the vertex cover number, which is linearly related to the number
of turns, and show that Colored Arc Kayles, BW-Arc Kayles, and Arc Kayles are
solved in time $O^*(1.4143^{\tau^2+3.17\tau})$, $O^*(1.3161^{\tau^2+4{\tau}})$,
and $O^*(1.1893^{\tau^2+6.34{\tau}})$, respectively, where $\tau$ is the vertex
cover number. Furthermore, we present an $O^*((n/\nu+1)^{\nu})$-time algorithm
for Arc Kayles, where $\nu$ is neighborhood diversity. We finally show that Arc
Kayles on trees can be solved in $O^* (2^{n/2})(=O(1.4143^n))$ time, which
improves $O^*(3^{n/3})(=O(1.4423^n))$ by a direct adjustment of the analysis of
Bodlaender et al.'s $O^*(3^{n/3})$-time algorithm for Node Kayles.
