P₃-Games

2016/08/18 by Hon, Wing-Kai, Kloks, Ton, Liu, Fu-Hong +2
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1608.05169

Abstract

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

Related

• P₃-Games on Chordal Bipartite Graphs
• Solving the General Case of Rank-3 Maker-Breaker Games in Polynomial Time
• Combinatorial Analysis of a Subtraction Game on Graphs
• The Polynomial Profile of Distance Games on Paths and Cycles
• The Game of Cycles for Grids and Select Theta Graphs