Tony Huynh

activity

20152022

most citedNotes on Aharoni's rainbow cycle conjecture

1 citations · 1 across the 6 of their papers we have counts for

collaborators

18 papers

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…

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

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

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

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…

Notes on Aharoni's rainbow cycle conjecture

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

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

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

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

Recognizing Cartesian products of matrices and polytopes

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