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

Northwestern University

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

Abstrakti

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

Alkuperäiskieli	Englanti
Otsikko	PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20)
Kustantaja	Society for Industrial and Applied Mathematics
Sivut	1955-1974
Sivumäärä	20
ISBN (elektroninen)	978-1-61197-599-4
DOI - pysyväislinkit	https://doi.org/10.1137/1.9781611975994.121
Tila	Julkaistu - 2020
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	ACM-SIAM Symposium on Discrete Algorithms - Salt Lake City, Yhdysvallat Kesto: 5 tammik. 2020 → 8 tammik. 2020 Konferenssinumero: 31

Conference

Conference	ACM-SIAM Symposium on Discrete Algorithms
Lyhennettä	SODA
Maa/Alue	Yhdysvallat
Kaupunki	Salt Lake City
Ajanjakso	05/01/2020 → 08/01/2020

Pääsy asiakirjaan

10.1137/1.9781611975994.121

https://arxiv.org/abs/2001.00257

OpenUrl-saatavuus

Koko teksti

Siteeraa tätä

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

publisher = "Society for Industrial and Applied Mathematics",

address = "United States",

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

}

Chalermsook, P, Khuller, S, Sukprasert, P & Uniyal, S 2020, Multi-transversals for Triangles and the Tuza's Conjecture. julkaisussa PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20). Society for Industrial and Applied Mathematics, Sivut 1955-1974, ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, Utah, Yhdysvallat, 05/01/2020. https://doi.org/10.1137/1.9781611975994.121

Multi-transversals for Triangles and the Tuza's Conjecture. / Chalermsook, Parinya; Khuller, Samir; Sukprasert, Pattara et al.

PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20). Society for Industrial and Applied Mathematics, 2020. s. 1955-1974.

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

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)

PB - Society for Industrial and Applied Mathematics

T2 - ACM-SIAM Symposium on Discrete Algorithms

Y2 - 5 January 2020 through 8 January 2020

ER -

Multi-transversals for Triangles and the Tuza's Conjecture

Abstrakti

Conference

Pääsy asiakirjaan

OpenUrl-saatavuus

Sormenjälki

Siteeraa tätä