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

45 papers

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…

cs.DM2021

Slack matrices, $k$ -products, and $2$ -level polytopes

Manuel Aprile, Michele Conforti, Yuri Faenza +3

In this paper, we study algorithmic questions concerning products of matrices and their consequences for recognition algorithms for polyhedra. The 1-product of matrices $S_{1}$ , $S_2…

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 $…

cs.DM2019★ 4 cited

Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles

Michele Conforti, Samuel Fiorini, Tony Huynh +1

Let $G$ be an $n$ -node graph without two disjoint odd cycles. The algorithm of Artmann, Weismantel and Zenklusen (STOC'17) for bimodular integer programs can be used to find a maxi…

cs.DM2019★ 1 cited

The stable set problem in graphs with bounded genus and bounded odd cycle packing number

Michele Conforti, Samuel Fiorin, Tony Huynh +2

Consider the family of graphs without $k$ node-disjoint odd cycles, where $k$ is a constant. Determining the complexity of the stable set problem for such graphs $G$ is a lon…

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.

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

Slack matrices, k-products, and 2-level polytopes

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

Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles

The stable set problem in graphs with bounded genus and bounded odd cycle packing number

Unavoidable minors for graphs with large ℓp​-dimension

Flip distances between graph orientations

The biclique covering number of grids

Slack matrices, $k$ -products, and $2$ -level polytopes

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