Multi-transversals for Triangles and the Tuza's Conjecture

Parinya Chalermsook, Samir Khuller, Pattara Sukprasert, Sumedha Uniyal

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

In this paper, we study a primal and dual relationship about triangles: For any graph G, let v(G) be the maximum number of edge-disjoint triangles in G, and tau(G) be the minimum subset F of edges such that G \ F is triangle-free. It is easy to see that v(G)

In this paper, we provide a proof of a non-trivial consequence of the conjecture; that is, for every k >= 2, there exist a (multi)-set F subset of E(G) : vertical bar F vertical bar

Original languageEnglish
Title of host publicationPROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20)
Pages1955-1974
Number of pages20
ISBN (Electronic)978-1-61197-599-4
DOIs
Publication statusPublished - 2020
MoE publication typeA4 Article in a conference publication
EventACM-SIAM Symposium on Discrete Algorithms - Salt Lake City, United States
Duration: 5 Jan 20208 Jan 2020
Conference number: 31

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA
CountryUnited States
CitySalt Lake City
Period05/01/202008/01/2020

Fingerprint Dive into the research topics of 'Multi-transversals for Triangles and the Tuza's Conjecture'. Together they form a unique fingerprint.

Cite this