Vida Dujmovic

activity

20242026

collaborators

Showing math.COShow all

3 papers · 1 filter

math.CO2026

Far-apart Erdős--Pósa property of long cycles

Maria Chudnovsky, Vida Dujmović, Gwenaël Joret +4

We prove that there exist functions $f : N^{2} \to N$ and $g : N \to N$ such that for all positive integers $k$ , $d$ , and $ℓ \geq 3$ , every graph $G$ either c…

math.CO2025

3-Colouring Planar Graphs

Vida Dujmović, Pat Morin, Sergey Norin +1

We show that every $n$ -vertex planar graph is 3-colourable with monochromatic components of size $O (n^{4/9})$ . The best previous bound was $O (n^{1/2})$ due to Linial, Matoušek, She…

math.CO2024

Erdős--Pósa property of cycles that are far apart

Vida Dujmović, Gwenaël Joret, Piotr Micek +1

We prove that there exist functions $f, g : N \to N$ such that for all nonnegative integers $k$ and $d$ , for every graph $G$ , either $G$ contains $k$ cycles such that…