Showing cs.DMShow all
2 papers · 1 filter
cs.DM2016
Convex Independence in Permutation Graphs
Wing-Kai Hon, Ton Kloks, Fu-Hong Liu +1
A set C of vertices of a graph is P_3-convex if every vertex outside C has at most one neighbor in C. The convex hull σ(A) of a set A is the smallest P_3-convex set that contains A…
cs.DM2016
P_3-Games
Wing-Kai Hon, Ton Kloks, Fu-Hong Liu +2
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…