Tony Huynh

activity

20122026

most citedA unified Erdős-Pósa theorem for constrained cycles

20 citations · 171 across the 37 of their papers we have counts for

collaborators

Showing math.COShow all

36 papers · 1 filter

math.CO2026

Countable Graphs with Finite Path-width: Characterisation and Universality

Tony Huynh, Freddie Illingworth, Nikolai Karol +4

We study path-width and the closely related parameter line-width in countably infinite graphs. Our first result characterises the graphs of finite path-width: they are the graphs t…

math.CO2023★ 7 cited

A Menger-type theorem for two induced paths

Sandra Albrechtsen, Tony Huynh, Raphael W. Jacobs +2

We give an approximate Menger-type theorem for when a graph $G$ contains two $X - Y$ paths $P_{1}$ and $P_{2}$ such that $P_{1} \cup P_{2}$ is an induced subgraph of $G$ . More generally, we…

math.CO2022★ 1 cited

Notes on Aharoni's rainbow cycle conjecture

Katie Clinch, Jackson Goerner, Tony Huynh +1

In 2017, Ron Aharoni made the following conjecture about rainbow cycles in edge-coloured graphs: If $G$ is an $n$ -vertex graph whose edges are coloured with $n$ colours and each co…

math.CO2022★ 5 cited

Product structure of graph classes with bounded treewidth

Rutger Campbell, Katie Clinch, Marc Distel +8

We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end…

math.CO2021★ 13 cited

Improved product structure for graphs on surfaces

Marc Distel, Robert Hickingbotham, Tony Huynh +1

Dujmović, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that for every graph $G$ with Euler genus $g$ there is a graph $H$ with treewidth at most 4 and a path $P$ suc…

math.CO2021★ 3 cited

Universality in minor-closed graph classes

Tony Huynh, Bojan Mohar, Robert Šámal +2

Stanislaw Ulam asked whether there exists a universal countable planar graph (that is, a countable planar graph that contains every countable planar graph as a subgraph). János Pac…

math.CO2021★ 7 cited

Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond

Manuel Aprile, Samuel Fiorini, Tony Huynh +2

Let $G$ be a connected $n$ -vertex graph in a proper minor-closed class $G$ . We prove that the extension complexity of the spanning tree polytope of $G$ is $O (n^{3/2})$ . Th…

math.CO2021

On the Erdős-Pósa property for long holes in $C_{4}$ -free graphs

Tony Huynh, O-joung Kwon

We prove that there exists a function $f (k) = O (k^{2} lo g k)$ such that for every $C_{4}$ -free graph $G$ and every $k \in N$ , $G$ either contains $k$ vertex-disjoint…

math.CO2020

A simple $(2 + ε)$ -approximation algorithm for Split Vertex Deletion

Matthew Drescher, Samuel Fiorini, Tony Huynh

A split graph is a graph whose vertex set can be partitioned into a clique and a stable set. Given a graph $G$ and weight function $w : V (G) \to Q_{\geq 0}$ , the Split Vert…

math.CO2020★ 11 cited

Tree densities in sparse graph classes

Tony Huynh, David R. Wood

What is the maximum number of copies of a fixed forest $T$ in an $n$ -vertex graph in a graph class $G$ as $n \to \infty$ ? We answer this question for a variety of sparse g…

math.CO2020

A simple 7/3-approximation algorithm for feedback vertex set in tournaments

Manuel Aprile, Matthew Drescher, Samuel Fiorini +1

We show that performing just one round of the Sherali-Adams hierarchy gives an easy 7/3-approximation algorithm for the Feedback Vertex Set (FVST) problem in tournaments. This matc…

math.CO2020

A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem

Manuel Aprile, Matthew Drescher, Samuel Fiorini +1

We give the first $2$ -approximation algorithm for the cluster vertex deletion problem. This is tight, since approximating the problem within any constant factor smaller than $2$ is…

math.CO2020★ 20 cited

Subgraph densities in a surface

Tony Huynh, Gwenaël Joret, David R. Wood

Given a fixed graph $H$ that embeds in a surface $Σ$ , what is the maximum number of copies of $H$ in an $n$ -vertex graph $G$ that embeds in $Σ$ ? We show that the answer is $Θ(n^{f(…

math.CO2020

Recognizing Cartesian products of matrices and polytopes

Manuel Aprile, Michele Conforti, Yuri Faenza +3

The 1-product of matrices $S_{1} \in R^{m_{1} \times n_{1}}$ and $S_{2} \in R^{m_{2} \times n_{2}}$ is the matrix in $R^{(m_{1} + m_{2}) \times (n_{1} n_{2})}$ whose columns ar…

math.CO2020

Notes on Tree- and Path-chromatic Number

Tony Huynh, Bruce Reed, David R. Wood +1

Tree-chromatic number is a chromatic version of treewidth, where the cost of a bag in a tree-decomposition is measured by its chromatic number rather than its size. Path-chromatic…

math.CO2020★ 5 cited

Excluding a ladder

Tony Huynh, Gwenaël Joret, Piotr Micek +2

A ladder is a $2 \times k$ grid graph. When does a graph class $C$ exclude some ladder as a minor? We show that this is the case if and only if all graphs $G$ in $\mathca…

math.CO2020★ 14 cited

Notes on Graph Product Structure Theory

Zdeněk Dvořák, Tony Huynh, Gwenaël Joret +2

It was recently proved that every planar graph is a subgraph of the strong product of a path and a graph with bounded treewidth. This paper surveys generalisations of this result f…

math.CO2019

Idealness of $k$ -wise intersecting families

Ahmad Abdi, Gérard Cornuéjols, Tony Huynh +1

A clutter is \emph{ $k$ -wise intersecting} if every $k$ members have a common element, yet no element belongs to all members. We conjecture that, for some integer $k \geq 4$ , every $…

math.CO2019

Unavoidable minors for graphs with large $ℓ_{p}$ -dimension

Samuel Fiorini, Tony Huynh, Gwenaël Joret +1

A metric graph is a pair $(G, d)$ , where $G$ is a graph and $d : E (G) \to R_{\geq 0}$ is a distance function. Let $p \in [1, \infty]$ be fixed. An isometric embedding of the met…

math.CO2019

Flip distances between graph orientations

Oswin Aichholzer, Jean Cardinal, Tony Huynh +4

Flip graphs are a ubiquitous class of graphs, which encode relations induced on a set of combinatorial objects by elementary, local changes. Skeletons of associahedra, for instance…

math.CO2018

The biclique covering number of grids

Krystal Guo, Tony Huynh, Marco Macchia

We determine the exact value of the biclique covering number for all grid graphs.

math.CO2018★ 8 cited

A tight Erdős-Pósa function for planar minors

Wouter Cames van Batenburg, Tony Huynh, Gwenaël Joret +1

Let $H$ be a planar graph. By a classical result of Robertson and Seymour, there is a function $f : N \to R$ such that for all $k \in N$ and all graphs $G$ …

math.CO2018

Short rainbow cycles in graphs and matroids

Matt DeVos, Matthew Drescher, Daryl Funk +5

Let $G$ be a simple $n$ -vertex graph and $c$ be a colouring of $E (G)$ with $n$ colours, where each colour class has size at least $2$ . We prove that $(G, c)$ contains a rainbow cycl…

math.CO2018★ 3 cited

Seymour's conjecture on 2-connected graphs of large pathwidth

Tony Huynh, Gwenaël Joret, Piotr Micek +1

We prove the conjecture of Seymour (1993) that for every apex-forest $H_{1}$ and outerplanar graph $H_{2}$ there is an integer $p$ such that every 2-connected graph of pathwidth at lea…

Countable Graphs with Finite Path-width: Characterisation and Universality

A Menger-type theorem for two induced paths

Notes on Aharoni's rainbow cycle conjecture

Product structure of graph classes with bounded treewidth

Improved product structure for graphs on surfaces

Universality in minor-closed graph classes

Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond

On the Erdős-Pósa property for long holes in C4​-free graphs

A simple (2+ε)-approximation algorithm for Split Vertex Deletion

Tree densities in sparse graph classes

A simple 7/3-approximation algorithm for feedback vertex set in tournaments

A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem

Subgraph densities in a surface

Recognizing Cartesian products of matrices and polytopes

Notes on Tree- and Path-chromatic Number

Excluding a ladder

Notes on Graph Product Structure Theory

Idealness of k-wise intersecting families

Unavoidable minors for graphs with large ℓp​-dimension

Flip distances between graph orientations

The biclique covering number of grids

A tight Erdős-Pósa function for planar minors

Short rainbow cycles in graphs and matroids

Seymour's conjecture on 2-connected graphs of large pathwidth

On the Erdős-Pósa property for long holes in $C_{4}$ -free graphs

A simple $(2 + ε)$ -approximation algorithm for Split Vertex Deletion

Idealness of $k$ -wise intersecting families

Unavoidable minors for graphs with large $ℓ_{p}$ -dimension