Search

Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds for graphs with small treewidth or small maximum average degree, including planar graphs. However, for dense graphs that are neither cliques nor 4-colorable, only asymptotic results are known. Here, we confirm the conjecture for threshold graphs, i.e. graphs that are both split graphs and cographs, and for co-chain graphs with both sides of the same size divisible by 4., Comment: 14 pages, 11 figures, Accepted to European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB) 2021

We consider the Erd\H{o}s-P\'osa property for immersions and topological minors in tournaments. We prove that for every simple digraph $H$, $k\in \mathbb{N}$, and tournament $T$, the following statements hold: (i) If in $T$ one cannot find $k$ arc-disjoint immersion copies of $H$, then there exists a set of $\mathcal{O}_H(k^3)$ arcs that intersects all immersion copies of $H$ in $T$. (ii) If in $T$ one cannot find $k$ vertex-disjoint topological minor copies of $H$, then there exists a set of $\mathcal{O}_H(k\log k)$ vertices that intersects all topological minor copies of $H$ in $T$. This improves the results of Raymond [DMTCS '18], who proved similar statements under the assumption that $H$ is strongly connected., Comment: 15 pages, 1 figure