Sylvain Gravier

collaborators

3 papers

cs.DM2026

Maker-Breaker is solved in polynomial time on hypergraphs of rank 3

Florian Galliot, Sylvain Gravier, Isabelle Sivignon

In the Maker-Breaker positional game, Maker and Breaker take turns picking vertices of a hypergraph $H$ , and Maker wins if and only if she possesses all the vertices of some edge o…

cs.DM2026

Some polynomial classes for the acyclic orientation with parity constraint problem

Sylvain Gravier, Matthieu Petiteau, Isabelle Sivignon

We study the problem of finding an acyclic orientation of an undirected graph with constrained in-degree parities specified by a subset T of vertices. An orientation is called T -o…

cs.DM2025

Note about the complexity of the acyclic orientation with parity constraint problem

Sylvain Gravier, Matthieu Petiteau, Isabelle Sivignon

Let $G = (V, E)$ be a connected graph, and let $T$ in $V$ be a subset of vertices. An orientation of $G$ is called $T$ -odd if any vertex $v \in V$ has odd in-degree if and only if…