4 papers
The Lovász Local Lemma Is Sharp for the Hat Guessing Number
Thomas Delépine, Matthieu Rosenfeld
In the hat guessing game on a graph , each vertex is occupied by a player wearing a hat whose color is chosen from a set of colors. Each player knows the graph and their pos…
The disjoint separators problem in graphs
Thomas Delépine, Florian Galliot, Yannick Mogge +2
We study the disjoint separators problem in graphs, an analogue of the famous disjoint paths problem. Given a graph and four pairwise disjoint subsets of vertices , ,…
Pairs of square-free arithmetic progressions in infinite words
Thomas Delépine, Pascal Ochem, Matthieu Rosenfeld
We study a question of Harju from 2019 regarding the existence of infinite ternary square-free words whose subsequences modulo and are also square-free for relatively prime…
Between proper and square coloring of planar graphs, hardness and extremal graphs
Thomas Delépine
-coloring is the problem of partitioning the vertex set of a graph into independent sets and 2-independent sets. This problem was recently introduced by Choi an…