Quentin Deschamps

activity

20212025

most citedSquare coloring planar graphs with automatic discharging

3 citations · 3 across the 8 of their papers we have counts for

collaborators

9 papers

cs.CC2025

The tape reconfiguration problem and its consequences for dominating set reconfiguration

Nicolas Bousquet, Quentin Deschamps, Arnaud Mary +2

A dominating set of a graph $G = (V, E)$ is a set of vertices $D \subseteq V$ whose closed neighborhood is $V$ , i.e., $N [D] = V$ . We view a dominating set as a collection of tokens plac…

cs.DS2023

Metric dimension parameterized by treewidth in chordal graphs

Nicolas Bousquet, Quentin Deschamps, Aline Parreau

The metric dimension has been introduced independently by Harary, Melter and Slater in 1975 to identify vertices of a graph G using its distances to a subset of vertices of G. A re…

math.CO2022

Incidence, a Scoring Positional Game on Graphs

Guillaume Bagan, Quentin Deschamps, Eric Duchêne +5

Positional games have been introduced by Hales and Jewett in 1963 and have been extensively investigated in the literature since then. These games are played on a hypergraph where…

math.CO2022★ 3 cited

Square coloring planar graphs with automatic discharging

Nicolas Bousquet, Lucas de Meyer, Quentin Deschamps +1

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 sometime…

math.CO2022

Partitioning into degenerate graphs in linear time

Timothée Corsini, Quentin Deschamps, Carl Feghali +3

Let $G$ be a connected graph with maximum degree $Δ \geq 3$ distinct from $K_{Δ + 1}$ . Generalizing Brooks' Theorem, Borodin, Kostochka and Toft proved that if $p_{1}, \dots, p_{s}$ are…

math.CO2022

Strengthening a theorem of Meyniel

Quentin Deschamps, Carl Feghali, František Kardoš +2

For an integer $k \geq 1$ and a graph $G$ , let $K_{k} (G)$ be the graph that has vertex set all proper $k$ -colorings of $G$ , and an edge between two vertices $α$ and~ $β$ whe…

math.CO2021

Improved square coloring of planar graphs

Nicolas Bousquet, Quentin Deschamps, Lucas de Meyer +1

Square coloring is a variant of graph coloring where vertices within distance two must receive different colors. When considering planar graphs, the most famous conjecture (Wegner,…

math.CO2021

Locating-dominating sets: from graphs to oriented graphs

Nicolas Bousquet, Quentin Deschamps, Tuomo Lehtilä +1

A locating-dominating set in an undirected graph is a subset of vertices $S$ such that $S$ is dominating and for every $u, v \in / S$ , we have $N (u) \cap S \neq = N (v) \cap S$ . In this p…

math.CO2021

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

Nicolas Bousquet, Quentin Deschamps, Aline Parreau +1

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$ …