activity
20242026
collaborators

7 papers

math.CO2026

Flow-critical graphs

Arnbjörg Soffía Árnadóttir, Zdeněk Dvořák, Bernard Lidický +3

Lovász et al. proved that every -edge-connected graph has a nowhere-zero -flow. In fact, they proved a more technical statement which says that there exists a nowhere zero $…

math.CO2025

Maximum -colourable induced subgraphs in -free graphs

Cicely Henderson, Evelyne Smith-Roberge, Sophie Spirkl +1

We show that for any nonnegative integer , the Weighted Maximum List--Colourable Induced Subgraph problem can be solved in polynomial time for input graphs that do not contai…

math.CO2025

Beyond the Pseudoforest Strong Nine Dragon Tree Theorem

Sebastian Mies, Benjamin Moore, Evelyne Smith-Roberge

The pseudoforest version of the Strong Nine Dragon Tree Conjecture states that if a graph has maximum average degree …

math.CO2025

Weak Degeneracy of Planar Graphs

Anton Bernshteyn, Eugene Lee, Evelyne Smith-Roberge

The weak degeneracy of a graph is a numerical parameter that was recently introduced by the first two authors with the aim of understanding the power of greedy algorithms for g…

math.CO2025

Local Weak Degeneracy of Planar Graphs

Ewan Davies, Evelyne Smith-Roberge

Thomassen showed that planar graphs are 5-list-colourable, and that planar graphs of girth at least five are 3-list-colourable. An easy degeneracy argument shows that planar graphs…

math.CO2024

Acyclic List Colouring Locally Planar Graphs

Luke Postle, Evelyne Smith-Roberge, Massimo Vicenzo

A (vertex) colouring of graph is \emph{acyclic} if it contains no bicoloured cycle. In 1979, Borodin proved that planar graphs are acyclically 5-colourable. In 2010, Kawarabayashi…