
A tight local algorithm for the minimum dominating set problem in outerplanar graphs
We show that there is a deterministic local algorithm (constanttime dis...
read it

On Vizing's edge colouring question
Soon after his 1964 seminal paper on edge colouring, Vizing asked the fo...
read it

Tuza's Conjecture for Threshold Graphs
Tuza famously conjectured in 1981 that in a graph without k+1 edgedisjo...
read it

On a recolouring version of Hadwiger's conjecture
We prove that for any ε>0, for any large enough t, there is a graph G th...
read it

Asymptotic Dimension of MinorClosed Families and AssouadNagata Dimension of Surfaces
The asymptotic dimension is an invariant of metric spaces introduced by ...
read it

Optimal labelling schemes for adjacency, comparability and reachability
We construct asymptotically optimal adjacency labelling schemes for ever...
read it

Limiting crossing numbers for geodesic drawings on the sphere
We introduce a model for random geodesic drawings of the complete bipart...
read it

A note on deterministic zombies
"Zombies and Survivor" is a variant of the wellstudied game of "Cops an...
read it

Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
Enumerating minimal transversals in a hypergraph is a notoriously hard p...
read it

On the effect of symmetry requirement for rendezvous on the complete graph
We consider a classic rendezvous game where two players try to meet each...
read it

Dominating sets reconfiguration under token sliding
Let G be a graph and D_s and D_t be two dominating sets of G of size k. ...
read it

Jones' Conjecture in subcubic graphs
We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic ...
read it

Graphs of bounded cliquewidth are polynomially χbounded
We prove that if C is a hereditary class of graphs that is polynomially ...
read it

Avoidable paths in graphs
We prove a recent conjecture of Beisegel et al. that for every positive ...
read it

Shorter Labeling Schemes for Planar Graphs
An adjacency labeling scheme for a given class of graphs is an algorithm...
read it

Every planar graph with Δ≥ 8 is totally (Δ+2)choosable
Total coloring is a variant of edge coloring where both vertices and edg...
read it

The Perfect Matching Reconfiguration Problem
We study the perfect matching reconfiguration problem: Given two perfect...
read it

Graph Isomorphism for (H_1,H_2)free Graphs: An Almost Complete Dichotomy
We consider the Graph Isomorphism problem for classes of graphs characte...
read it

Colouring Graphs with Sparse Neighbourhoods: Bounds and Applications
Let G be a graph with chromatic number χ, maximum degree Δ and clique nu...
read it

Enumerating minimal dominating sets in trianglefree graphs
It is a longstanding open problem whether the minimal dominating sets o...
read it

EPTAS for Max Clique on Disks and Unit Balls
We propose a polynomialtime algorithm which takes as input a finite set...
read it

Distributed Recoloring
Given two colorings of a graph, we consider the following problem: can w...
read it

Distributed coloring in sparse graphs with fewer colors
This paper is concerned with efficiently coloring sparse graphs in the d...
read it

On Directed Feedback Vertex Set parameterized by treewidth
We study the Directed Feedback Vertex Set problem parameterized by the t...
read it
Marthe Bonamy
is this you? claim profile