Packing and covering directed triangles asymptotically

J 2022

Packing and covering directed triangles asymptotically

COOPER, Jacob, Andrzej GRZESIK, Adam KABELA and Daniel KRÁĽ

Basic information

Original name

Packing and covering directed triangles asymptotically

Authors

COOPER, Jacob (826 United Kingdom of Great Britain and Northern Ireland, belonging to the institution), Andrzej GRZESIK, Adam KABELA (203 Czech Republic, belonging to the institution) and Daniel KRÁĽ (203 Czech Republic, guarantor, belonging to the institution)

Edition

European Journal of Combinatorics, LONDON, ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2022, 0195-6698

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Netherlands

Confidentiality degree

není předmětem státního či obchodního tajemství

References:

URL

Impact factor

Impact factor: 1.000

RIV identification code

RIV/00216224:14330/22:00125213

Organization unit

Faculty of Informatics

DOI

http://dx.doi.org/10.1016/j.ejc.2021.103462

UT WoS

000721356900012

Keywords in English

directed graphs

Abstract

V originále

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.

Links

MUNI/A/1108/2020, interní kód MU

Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X. (Acronym: SV-FI MAV X.)

Investor: Masaryk University

MUNI/A/1145/2021, interní kód MU

Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI. (Acronym: SV-FI MAV XI.)

Investor: Masaryk University

MUNI/I/1677/2018, interní kód MU

Name: MUNI AWARD in Science and Humanitites 1 (Acronym: MASH 1)

Investor: Masaryk University, MASH - MUNI Award in Science and Humanities

Citovat

COOPER, Jacob, Andrzej GRZESIK, Adam KABELA and Daniel KRÁĽ. Packing and covering directed triangles asymptotically. European Journal of Combinatorics. LONDON: ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2022, vol. 101, No 103462, p. 1-9. ISSN 0195-6698. Available from: https://dx.doi.org/10.1016/j.ejc.2021.103462.

@article{1824821,
   author = {Cooper, Jacob and Grzesik, Andrzej and Kabela, Adam and Kráľ, Daniel},
   article_location = {LONDON},
   article_number = {103462},
   doi = {http://dx.doi.org/10.1016/j.ejc.2021.103462},
   keywords = {directed graphs},
   language = {eng},
   issn = {0195-6698},
   journal = {European Journal of Combinatorics},
   title = {Packing and covering directed triangles asymptotically},
   url = {https://www.sciencedirect.com/science/article/pii/S0195669821001566},
   volume = {101},
   year = {2022}
}

TY  - JOUR
ID  - 1824821
AU  - Cooper, Jacob - Grzesik, Andrzej - Kabela, Adam - Kráľ, Daniel
PY  - 2022
TI  - Packing and covering directed triangles asymptotically
JF  - European Journal of Combinatorics
VL  - 101
IS  - 103462
SP  - 1-9
EP  - 1-9
PB  - ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
SN  - 01956698
KW  - directed graphs
UR  - https://www.sciencedirect.com/science/article/pii/S0195669821001566
N2  - 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.
ER  -

COOPER, Jacob, Andrzej GRZESIK, Adam KABELA and Daniel KRÁĽ. Packing and covering directed triangles asymptotically. \textit{European Journal of Combinatorics}. LONDON: ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2022, vol.~101, No~103462, p.~1-9. ISSN~0195-6698. Available from: https://dx.doi.org/10.1016/j.ejc.2021.103462.

Detailed Information on Publication Record