research
∙
03/14/2023
A note on the flip distance between non-crossing spanning trees
We consider spanning trees of n points in convex position whose edges ar...
share
research
∙
01/05/2023
A note on highly connected K_2,ℓ-minor free graphs
We show that every 3-connected K_2,ℓ-minor free graph with minimum degre...
research
∙
01/05/2023
Extremal Independent Set Reconfiguration
The independent set reconfiguration problem asks whether one can transfo...
research
∙
10/18/2022
The smallest 5-chromatic tournament
A coloring of a digraph is a partition of its vertex set such that each ...
research
∙
04/12/2022
Square coloring planar graphs with automatic discharging
The discharging method is a powerful proof technique, especially for gra...
research
∙
02/12/2022
What can be certified compactly?
Local certification consists in assigning labels (called certificates) t...
research
∙
01/19/2022
Strengthening a theorem of Meyniel
For an integer k ≥ 1 and a graph G, let 𝒦_k(G) be the graph that has ver...
research
∙
10/20/2021
Improved pyrotechnics : Closer to the burning graph conjecture
Can every connected graph burn in ⌈√(n)⌉ steps? While this conjecture re...
research
∙
10/05/2021
Local certification of MSO properties for bounded treedepth graphs
The graph model checking problem consists in testing whether an input gr...
research
∙
07/30/2021
Local certification of graph decompositions and applications to minor-free classes
Local certification consists in assigning labels to the nodes of a netwo...
research
∙
05/20/2021
(Sub)linear kernels for edge modification problems towards structured graph classes
In a (parameterized) graph edge modification problem, we are given a gra...
research
∙
09/25/2020
On the signed chromatic number of some classes of graphs
A signed graph (G, σ) is a graph G along with a function σ: E(G) →{+,-}....
research
∙
12/24/2019
A Brooks-like result for graph powers
Coloring a graph G consists in finding an assignment of colors c: V(G)→{...
research
∙
11/22/2019
Pushable chromatic number of graphs with degree constraints
Pushable homomorphisms and the pushable chromatic number χ_p of oriented...
research
∙
10/02/2019
Parameterized complexity of edge-coloured and signed graph homomorphism problems
We study the complexity of graph modification problems for homomorphism-...
research
∙
07/07/2019
Complexity of planar signed graph homomorphisms to cycles
We study homomorphism problems of signed graphs. A signed graph is an un...
research
∙
04/26/2019