Multi-transversals for Triangles and the Tuza's Conjecture

Parinya Chalermsook; Samir Khuller; Pattara Sukprasert; Sumedha Uniyal

doi:10.1137/1.9781611975994.121

Multi-transversals for Triangles and the Tuza's Conjecture

Parinya Chalermsook, Samir Khuller, Pattara Sukprasert, Sumedha Uniyal

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-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 language	English
Title of host publication	PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20)
Pages	1955-1974
Number of pages	20
ISBN (Electronic)	978-1-61197-599-4
DOIs	https://doi.org/10.1137/1.9781611975994.121
Publication status	Published - 2020
MoE publication type	A4 Article in a conference publication
Event	ACM-SIAM Symposium on Discrete Algorithms - Salt Lake City, United States Duration: 5 Jan 2020 → 8 Jan 2020 Conference number: 31

Conference

Conference	ACM-SIAM Symposium on Discrete Algorithms
Abbreviated title	SODA
Country	United States
City	Salt Lake City
Period	05/01/2020 → 08/01/2020

Access to Document

10.1137/1.9781611975994.121

https://arxiv.org/abs/2001.00257

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

Cite this

@inproceedings{71858a831c744981b5fcee6be6238d04,

title = "Multi-transversals for Triangles and the Tuza's Conjecture",

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",

author = "Parinya Chalermsook and Samir Khuller and Pattara Sukprasert and Sumedha Uniyal",

year = "2020",

doi = "10.1137/1.9781611975994.121",

language = "English",

pages = "1955--1974",

booktitle = "PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20)",

note = "ACM-SIAM Symposium on Discrete Algorithms, SODA ; Conference date: 05-01-2020 Through 08-01-2020",

}

TY - GEN

T1 - Multi-transversals for Triangles and the Tuza's Conjecture

AU - Chalermsook, Parinya

AU - Khuller, Samir

AU - Sukprasert, Pattara

AU - Uniyal, Sumedha

N1 - Conference code: 31

PY - 2020

Y1 - 2020

N2 - 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

AB - 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

U2 - 10.1137/1.9781611975994.121

DO - 10.1137/1.9781611975994.121

M3 - Conference contribution

SP - 1955

EP - 1974

BT - PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20)

T2 - ACM-SIAM Symposium on Discrete Algorithms

Y2 - 5 January 2020 through 8 January 2020

ER -