A291341 Number of nonisomorphic graphs on n vertices that are first-player-winning in the game of Col.

1, 0, 2, 4, 13, 52, 398, 4454, 85658, 3283444

Offset

1,3

Comments

The game of Col was studied by John Conway. It is played on a map. Here we slightly generalize the game so that players color the vertices of a graph.

References

Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, Winning Ways for your Mathematical Plays (Vol. 1), Academic Press, New York, 1982, pages 37-39.

Links

Table of n, a(n) for n=1..10.

Wikipedia, The game of Col

Example

For n=3, there are 4 nonisomorphic graphs on 3 vertices, containing 0, 1, 2, or 3 edges respectively. Among them, the graphs with 0 or 1 edge are first-player-winning. Hence, a(3)=2.

Mathematica

(* We need to download the database of nonisomorphic simple graphs from http://users.cecs.anu.edu.au/~bdm/data/graphs.html
Assume that we have saved the file of nonisomorphic simple graphs with 10 vertices as "/.../10vertices.txt." *)
rawdata = Import["/.../10vertices.txt", "Lines"];    length = Length[rawdata];
rawdata2 = Rest /@ ToCharacterCode[rawdata] - 63;
DectoBin[n_] := IntegerDigits[n, 2, 6];
rawdata3 = Table[Flatten[DectoBin /@ row][[;; -4]], {row, rawdata2}];
n = 10; edges =  Table[Complement[   row*{1 <-> 2, 1 <-> 3, 2 <-> 3, 1 <-> 4, 2 <-> 4, 3 <-> 4, 1 <-> 5, 2 <-> 5, 3 <-> 5, 4 <-> 5, 1 <-> 6, 2 <-> 6, 3 <-> 6, 4 <-> 6, 5 <-> 6, 1 <-> 7, 2 <-> 7, 3 <-> 7, 4 <-> 7, 5 <-> 7, 6 <-> 7, 1 <-> 8, 2 <-> 8, 3 <-> 8, 4 <-> 8, 5 <-> 8, 6 <-> 8, 7 <-> 8, 1 <-> 9, 2 <-> 9, 3 <-> 9, 4 <-> 9, 5 <-> 9, 6 <-> 9, 7 <-> 9, 8 <-> 9, 1 <-> 10, 2 <-> 10, 3 <-> 10, 4 <-> 10, 5 <-> 10, 6 <-> 10, 7 <-> 10, 8 <-> 10, 9 <-> 10}, {0}], {row, rawdata3}];
winning = Table[0, {i, length}];
Renew :=  Block[{},
  Nocolor = Complement[Range[n], Alist, Blist];
  Anonneighbor =    Complement[Nocolor,     Flatten[Select[graph, Length[Complement[#, Alist]] < 2 &]]];
  Bnonneighbor =    Complement[Nocolor,     Flatten[Select[graph, Length[Complement[#, Blist]] < 2 &]]];
  Anextmove =    Complement[Anonneighbor, Aforbidden[[Length[Alist] + 1]]];
  Bnextmove =    Complement[Bnonneighbor, Bforbidden[[Length[Blist] + 1]]]];
Do[graph = edges[[j]]; Alist = {}; Blist = {};    Aforbidden = Table[{}, {i, Ceiling[n/2] + 1}];    Bforbidden = Table[{}, {i, Floor[n/2] + 1}]; Renew;
  While[!MemberQ[Aforbidden[[1]], n] && !MemberQ[Bforbidden[[1]], n] && Length[Union[Alist, Bforbidden[[1]]]] != n,
    If[Anextmove != {} && Length[Alist] == Length[Blist],    AppendTo[Alist, Anextmove[[1]]]; Renew];
    If[Bnextmove != {} && Length[Alist] - 1 == Length[Blist],    AppendTo[Blist, Bnextmove[[1]]]; Renew];
    If[Anextmove == {} && Length[Alist] == Length[Blist],    AppendTo[Aforbidden[[Length[Alist]]], Alist[[-1]]];
    Aforbidden[[Length[Alist] + 1 ;; ]] = {};
    Alist = Most[Alist];
    Bforbidden[[Length[Blist] ;; ]] = {};
    Blist = Most[Blist]; Renew];
  If[Bnextmove == {} && Length[Alist] - 1 == Length[Blist],
    AppendTo[Bforbidden[[Length[Blist]]], Blist[[-1]]];
    Bforbidden[[Length[Blist] + 1 ;; ]] = {};
    Blist = Most[Blist];
    Aforbidden[[Length[Alist] ;; ]] = {};
    Alist = Most[Alist]; Renew];
  If[MemberQ[Bforbidden[[1]], n] ||     Length[Union[Alist, Bforbidden[[1]]]] == n, winning[[j]] = 1]],
{j, length}];
Total @ winning

Crossrefs

A291342 gives the number of labeled graphs on n vertices that are first-player-winning in the game of Col.

Sequence in context: A030917 A030863 A030800 * A385265 A129091 A030970

Adjacent sequences: A291338 A291339 A291340 * A291342 A291343 A291344

Keyword

nonn,more

Author

Diego A. Manzano-Ruiz, Wing Hong Tony Wong, Aug 22 2017

Status

approved