×

One-color triangle avoidance games. (English) Zbl 0990.91008

In the triangle avoidance game two players take turns to add edges to a graph which initially consists of \(n\) nodes and no edges. The first player to complete a triangle (3-cycle) loses. This paper describes a computation to determine which player has a winning strategy when \(n\leq 12\). The winner for \(n\leq 9\) had previously been determined by Á. Seress [Graphs Comb. 8, No. 1, 75-79 (1992; Zbl 0757.90096)]. The authors also solve the simple game in which the aim is to avoid creating any cycle of odd-length, showing that the first player to move wins when \(n\) is 2 modulo 4 and otherwise the second player wins.

MSC:

91A43 Games involving graphs
05C20 Directed graphs (digraphs), tournaments

Citations:

Zbl 0757.90096
PDFBibTeX XMLCite