Packing and covering directed triangles asymptotically

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

COOPER Jacob GRZESIK Andrzej KABELA Adam KRÁĽ Daniel

Year of publication 2022
Type Article in Periodical
Magazine / Source European Journal of Combinatorics
MU Faculty or unit

Faculty of Informatics

Citation
Web https://www.sciencedirect.com/science/article/pii/S0195669821001566
Doi http://dx.doi.org/10.1016/j.ejc.2021.103462
Keywords directed graphs
Description A well-known conjecture of Tuza asserts that if a graph has at most t pairwise edge-disjoint triangles, then it can be made triangle-free by removing at most 2t edges. If true, the factor 2 would be best possible. In the directed setting, also asked by Tuza, the analogous statement has recently been proven, however, the factor 2 is not optimal. In this paper, we show that if an n-vertex directed graph has at most t pairwise arc-disjoint directed triangles, then there exists a set of at most 1.8t + o(n(2)) arcs that meets all directed triangles. We complement our result by presenting two constructions of large directed graphs with t is an element of Omega(n(2)) whose smallest such set has 1.5t - o(n(2)) arcs. (C) 2021 Elsevier Ltd. All rights reserved.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.