research
∙
02/26/2023
Partitioning edges of a planar graph into linear forests and a matching
We show that the edges of any planar graph of maximum degree at most 9 c...
share
research
∙
01/20/2023
Separating the edges of a graph by a linear number of paths
Recently, Letzter proved that any graph of order n contains a collection...
research
∙
06/01/2022
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
A graph is O_k-free if it does not contain k pairwise vertex-disjoint an...
research
∙
12/04/2021
Kempe changes in degenerate graphs
We consider Kempe changes on the k-colorings of a graph on n vertices. I...
research
∙
10/28/2021
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
A (unit) disk graph is the intersection graph of closed (unit) disks in ...
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
∙
08/05/2021
A tight local algorithm for the minimum dominating set problem in outerplanar graphs
We show that there is a deterministic local algorithm (constant-time dis...
research
∙
07/16/2021
On Vizing's edge colouring question
Soon after his 1964 seminal paper on edge colouring, Vizing asked the fo...
research
∙
05/20/2021
Tuza's Conjecture for Threshold Graphs
Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjo...
research
∙
03/19/2021
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...
research
∙
12/04/2020
Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces
The asymptotic dimension is an invariant of metric spaces introduced by ...
research
∙
12/03/2020
Optimal labelling schemes for adjacency, comparability and reachability
We construct asymptotically optimal adjacency labelling schemes for ever...
research
∙
08/24/2020
Limiting crossing numbers for geodesic drawings on the sphere
We introduce a model for random geodesic drawings of the complete bipart...
research
∙
08/08/2020
A note on deterministic zombies
"Zombies and Survivor" is a variant of the well-studied game of "Cops an...
research
∙
04/15/2020
Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
Enumerating minimal transversals in a hypergraph is a notoriously hard p...
research
∙
02/10/2020
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...
research
∙
12/06/2019
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. ...
research
∙
12/03/2019
Jones' Conjecture in subcubic graphs
We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic ...
research
∙
10/01/2019
Graphs of bounded cliquewidth are polynomially χ-bounded
We prove that if C is a hereditary class of graphs that is polynomially ...
research
∙
08/10/2019
Avoidable paths in graphs
We prove a recent conjecture of Beisegel et al. that for every positive ...
research
∙
08/09/2019
Shorter Labeling Schemes for Planar Graphs
An adjacency labeling scheme for a given class of graphs is an algorithm...
research
∙
04/26/2019
Every planar graph with Δ≥ 8 is totally (Δ+2)-choosable
Total coloring is a variant of edge coloring where both vertices and edg...
research
∙
04/12/2019
The Perfect Matching Reconfiguration Problem
We study the perfect matching reconfiguration problem: Given two perfect...
research
∙
11/29/2018
Graph Isomorphism for (H_1,H_2)-free Graphs: An Almost Complete Dichotomy
We consider the Graph Isomorphism problem for classes of graphs characte...
research
∙
10/15/2018
Colouring Graphs with Sparse Neighbourhoods: Bounds and Applications
Let G be a graph with chromatic number χ, maximum degree Δ and clique nu...
research
∙
10/01/2018
Enumerating minimal dominating sets in triangle-free graphs
It is a long-standing open problem whether the minimal dominating sets o...
research
∙
03/05/2018
EPTAS for Max Clique on Disks and Unit Balls
We propose a polynomial-time algorithm which takes as input a finite set...
research
∙
02/19/2018
Distributed Recoloring
Given two colorings of a graph, we consider the following problem: can w...
research
∙
02/15/2018
Distributed coloring in sparse graphs with fewer colors
This paper is concerned with efficiently coloring sparse graphs in the d...
research
∙
07/05/2017