The graph coloring game is a famous two-player game (re)introduced by Bodlaender in 1991. Given a graph G and k ∈ N, Alice and Bob alternately (starting with Alice) color an uncolored vertex with some color in {1, • • • , k} such that no two adjacent vertices receive a same color. If eventually all vertices are colored, then Alice wins and Bob...
-
2024 (v1)ReportUploaded on: January 13, 2025
-
2024 (v1)Report
In 1984, Frank Harary introduced the first graph convexity game, focused on the geodesic convexity. A set S ⊆ V of vertices of a graph G = (V, E) is convex if every shortest path between two vertices of S is also included in S. We introduce the Convex Set Forming Game CFG: two players alternately select vertices in such a way that the set of...
Uploaded on: September 27, 2024