24 citations · 65 across the 21 of their papers we have counts for
25 papers
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…
Note about the complexity of the acyclic orientation with parity constraint problem
Sylvain Gravier, Matthieu Petiteau, Isabelle Sivignon
Let be a connected graph, and let in be a subset of vertices. An orientation of is called -odd if any vertex has odd in-degree if and only if…
An update on the coin-moving game on the square grid
Florian Galliot, Sylvain Gravier, Isabelle Sivignon
This paper extends the work started in 2002 by Demaine, Demaine and Verill (DDV) on coin-moving puzzles. These puzzles have a long history in the recreational literature, but were…
(k-2)-linear connected components in hypergraphs of rank k
Florian Galliot, Sylvain Gravier, Isabelle Sivignon
We define a -linear path in a hypergraph as a sequence of edges of such that and if $|…
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 , and Maker wins if and only if she possesses all the vertices of some edge o…
Optimal Adjacent Vertex-Distinguishing Edge-Colorings of Circulant Graphs
Sylvain Gravier, Hippolyte Signargout, Souad Slimani
A -proper edge-coloring of a graph G is called adjacent vertex-distinguishing if any two adjacent vertices are distinguished by the set of colors appearing in the edges incident…