SuperHyperGraph Coloring Game and SuperHyperGraphDomination Game

Resumen

A finite hypergraph generalizes an ordinary graph by allowing each hyperedge to connect an arbitrary
nonempty subset of vertices, thereby modeling genuinely multiway interactions. Taking this idea one step
further, a finite SuperHyperGraph is obtained by iterating the powerset construction: set-valued objects created
at one level can serve as vertices (or edge endpoints) at the next. This yields a principled formalism for
hierarchical, multi-layer relational structure.
Vertex coloring is a classical theme in graph theory. One assigns colors to vertices so that adjacent vertices
receive distinct colors and seeks to minimize the number of colors used, namely the chromatic number. In
parallel, there is a broad literature on coloring games and coloring dynamics, where colors evolve through local
updates governed either by competing players (as in game-chromatic variants) or by prescribed interaction
rules (as in stochastic or rule-based recoloring processes). In particular, what is often called the HyperGraph
Coloring Game in the dynamical setting is not a two-player optimization game, but rather a local recoloring
process (typically a finite-state Markov chain) whose transitions are determined by selecting a hyperedge and
updating colors on that hyperedge according to a specified rule. By contrast, the Graph Domination Game is
a genuine two-player game: players alternately select vertices, each move must newly dominate at least one
previously undominated vertex (the chosen vertex or one of its neighbors), and Dominator aims to finish in as
few moves as possible.
In this paper, we introduce two further generalizations within the powerset-based SuperHyperGraph frame-
work. First, we define the SuperHyperGraph Coloring Game as a natural SuperHyperGraph-level analogue
of the HyperGraph recoloring process, and we explicitly interpret it as a coloring dynamics on supervertices.
Second, we define the SuperHyperGraph Domination Game as an extension of the HyperGraph Domination
Game.