P_3-Games

Abstract

Without further ado, we present the P_3-game. The P_3-game is decidable for elementary classes of graphs such as paths and cycles. From an algorithmic point of view, the connected P_3-game is fascinating. We show that the connected P_3-game is polynomially decidable for classes such as trees, chordal graphs, ladders, cacti, outerplanar graphs and circular arc graphs.