BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Quentin Deschamps

Quentin Deschamps appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CODiscrete Mathematics

Catalog footprint

What is connected

5works
2topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

5 published item(s)

preprint2026arXiv

Token positional games

The classical Maker-Breaker positional game is played on a board which is a hypergraph $\mathcal{H}$, with two players, Maker and Breaker, alternately claiming vertices of $\mathcal{H}$ until all the vertices are claimed. When the game ends, Maker wins if she has claimed all the vertices of some edge of $\mathcal{H}$; otherwise, Breaker wins. Playing this game in real life can be done by placing tokens on the vertices of the board. In this paper, we study the unfortunate case in which one or both players do not have enough tokens to cover all the vertices and, as such, will have to move their tokens around at some point instead of placing new ones. There may be a bias, in that Maker and Breaker do not necessarily have the same amount of tokens. The present paper initiates the study of this generalization of positional games, called token positional games. A particularly interesting case is when Maker has a winning strategy in the classical game: what is the lowest number of tokens with which she still wins against Breaker's unlimited stock? We notably show that, for $k$-uniform hypergraphs on an arbitrarily large number $n$ of vertices, this number equals $k$ if $k \in\{2,3\}$ but can vary from $k$ to $Ω(n)$ if $k \geq 4$. From an algorithmic point of view, PSPACE-hardness in general is inherited from classical positional games, but we get a polynomial-time algorithm to solve the case where Breaker only has one token. We also establish EXPTIME-completeness for a "token sliding" variation of the game.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Locating-dominating sets: from graphs to oriented graphs

A locating-dominating set in an undirected graph is a subset of vertices $S$ such that $S$ is dominating and for every $u,v \notin S$, we have $N(u)\cap S\ne N(v)\cap S$. In this paper, we consider the oriented version of the problem. A locating-dominating set in an oriented graph is a set $S$ such that for every $w\in V$, $N[w]^-\cap S=\emptyset$ and for each pair of vertices $u,v\in V\setminus S$, $N^-(u)\cap S\ne N^-(v)\cap S$. We consider the following two parameters. Given an undirected graph $G$, we look for $\overset{\rightarrow}γ_{LD}(G)$ ($\overset{\rightarrow}Γ_{LD}(G))$ which is the size of the smallest (largest) optimal locating-dominating set over all orientations of $G$. In particular, if $D$ is an orientation of $G$, then $\overset{\rightarrow}γ_{LD}(G)\leqγ_{LD}(D)\leq\overset{\rightarrow}Γ_{LD}(G)$. For the best orientation, we prove that, for every twin-free graph $G$ on $n$ vertices, $\overset{\rightarrow}γ_{LD}(G)\le n/2$ proving a ``directed version'' of a conjecture on $γ_{LD}(G)$. Moreover, we give some bounds for $\overset{\rightarrow}γ_{LD}(G)$ on many graph classes and drastically improve the value $n/2$ for (almost) $d$-regular graphs by showing that $\overset{\rightarrow}γ_{LD}(G)\in O(\log d/d\cdot n)$ using a probabilistic argument. While $\overset{\rightarrow}γ_{LD}(G)\leqγ_{LD}(G)$ holds for every graph $G$, we give some graph classes graphs for which $\overset{\rightarrow}Γ_{LD}(G)\geqγ_{LD}(G)$ and some for which $\overset{\rightarrow}Γ_{LD}(G)\leq γ_{LD}(G)$. We also give general bounds for $\overset{\rightarrow}Γ_{LD}(G)$. Finally, we show that for many graph classes $\overset{\rightarrow}Γ_{LD}(G)$ is polynomial on $n$ but we leave open the question whether there exist graphs with $\overset{\rightarrow}Γ_{LD}(G)\in O(\log n)$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Metric dimension on sparse graphs and its applications to zero forcing sets

The metric dimension dim(G) of a graph $G$ is the minimum cardinality of a subset $S$ of vertices of $G$ such that each vertex of $G$ is uniquely determined by its distances to $S$. It is well-known that the metric dimension of a graph can be drastically increased by the modification of a single edge. Our main result consists in proving that the increase of the metric dimension of an edge addition can be amortized in the sense that if the graph consists of a spanning tree $T$ plus $c$ edges, then the metric dimension of $G$ is at most the metric dimension of $T$ plus $6c$. We then use this result to prove a weakening of a conjecture of Eroh et al. The zero forcing number $Z(G)$ of $G$ is the minimum cardinality of a subset $S$ of black vertices (whereas the other vertices are colored white) of $G$ such that all the vertices will turned black after applying finitely many times the following rule: a white vertex is turned black if it is the only white neighbor of a black vertex. Eroh et al. conjectured that, for any graph $G$, $dim(G)\leq Z(G) + c(G)$, where $c(G)$ is the number of edges that have to be removed from $G$ to get a forest. They proved the conjecture is true for trees and unicyclic graphs. We prove a weaker version of the conjecture: $dim(G)\leq Z(G)+6c(G)$ holds for any graph. We also prove that the conjecture is true for graphs with edge disjoint cycles, widely generalizing the unicyclic result of Eroh et al.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Square coloring planar graphs with automatic discharging

The discharging method is a powerful proof technique, especially for graph coloring problems. Its major downside is that it often requires lengthy case analyses, which are sometimes given to a computer for verification. However, it is much less common to use a computer to actively look for a discharging proof. In this paper, we use a Linear Programming approach to automatically look for a discharging proof. While our system is not entirely autonomous, we manage to make some progress towards Wegner's conjecture for distance-$2$ coloring of planar graphs, by showing that $12$ colors are sufficient to color at distance $2$ every planar graph with maximum degree $4$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Strengthening a theorem of Meyniel

For an integer $k \geq 1$ and a graph $G$, let $\mathcal{K}_k(G)$ be the graph that has vertex set all proper $k$-colorings of $G$, and an edge between two vertices $α$ and~$β$ whenever the coloring~$β$ can be obtained from $α$ by a single Kempe change. A theorem of Meyniel from 1978 states that $\mathcal{K}_5(G)$ is connected with diameter $O(5^{|V(G)|})$ for every planar graph $G$. We significantly strengthen this result, by showing that there is a positive constant $c$ such that $\mathcal{K}_5(G)$ has diameter $O(|V(G)|^c)$ for every planar graph $G$.

0 citations0 reviewsNo code linkedOpen access