Pat Morin

activity

20232026

collaborators

Showing math.COShow all

9 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.CO2026

3-Colouring Graphs Excluding a Fixed Minor

Vida Dujmović, Hussein Houdrouge, Pat Morin

We show that, for every fixed graph $H$ , every $n$ -vertex graph $G$ that excludes $H$ as a minor is $3$ -colourable with clustering $O_{H} (n^{4/9})$ . That is, there exists a function…

math.CO2026

2-dimensional unit vector flows

Hussein Houdrouge, Bobby Miraftab, Pat Morin

We study $2$ -dimensional unit vector flows on graphs, that is, nowhere-zero flows that assign to each oriented edge a unit vector in $R^{3}$ . We give a new geometric charac…

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…

math.CO2024

On $k$ -planar Graphs without Short Cycles

Michael A. Bekos, Prosenjit Bose, Aaron Büngener +6

We study the impact of forbidding short cycles to the edge density of $k$ -planar graphs; a $k$ -planar graph is one that can be drawn in the plane with at most $k$ crossings per edg…

math.CO2024

Planar graphs in blowups of fans

Marc Distel, Vida Dujmović, Gwenaël Joret +3

We show that every $n$ -vertex planar graph is contained in the graph obtained from a fan by blowing up each vertex by a complete graph of order $O (n lo g^{2} n)$ . Equivalently,…

math.CO2024

Vertex Ranking of Degenerate Graphs

John Iacono, Piotr Micek, Pat Morin +1

An $ℓ$ -vertex-ranking of a graph $G$ is a colouring of the vertices of $G$ with integer colours so that in any connected subgraph $H$ of $G$ with diameter at most $ℓ$ , there…

math.CO2024

Grid Minors and Products

Vida Dujmović, Pat Morin, David R. Wood +1

Motivated by recent developments regarding the product structure of planar graphs, we study relationships between treewidth, grid minors, and graph products. We show that the Carte…

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

3-Colouring Graphs Excluding a Fixed Minor

2-dimensional unit vector flows

3-Colouring Planar Graphs

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

On k-planar Graphs without Short Cycles

Planar graphs in blowups of fans

Vertex Ranking of Degenerate Graphs

Grid Minors and Products

On $k$ -planar Graphs without Short Cycles