On Tuza's Conjecture for Triangulations and Graphs with Small Treewidth

F. Botler; C. G. Fernandes; J. Gutiérrez

doi:10.1016/j.entcs.2019.08.016

On Tuza's Conjecture for Triangulations and Graphs with Small Treewidth

F. Botler, C. G. Fernandes, J. Gutiérrez

Producción científica: Contribución a una revista › Artículo de la conferencia › revisión exhaustiva

4 Citas (Scopus)

Resumen

Tuza (1981) conjectured that the cardinality τ(G) of a minimum set of edges that intersects every triangle of a graph G is at most twice the cardinality ν(G) of a maximum set of edge-disjoint triangles of G. I this paper we present three results regarding Tuza's Conjecture. We verify it for graphs with treewidth at most 6; and we show that _{^{τ(G)≤32ν(G)}} for every planar triangulation G different from K₄; and that _{^{τ(G)≤95ν(G)+15}} if G is a maximal graph with treewidth 3.

Idioma original	Inglés
Páginas (desde-hasta)	171-183
Número de páginas	13
Publicación	Electronic Notes in Theoretical Computer Science
Volumen	346
DOI	https://doi.org/10.1016/j.entcs.2019.08.016
Estado	Publicada - 2019
Publicado de forma externa	Sí
Evento	10th Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2019 - Belo Horizonte, Brasil Duración: 2 jun. 2019 → 7 jun. 2019

Acceder al documento

10.1016/j.entcs.2019.08.016

Otros archivos y enlaces

Enlace a la publicación en Scopus

Citar esto

@article{91c22f4e31c446df96fbd1165a7350ab,

title = "On Tuza's Conjecture for Triangulations and Graphs with Small Treewidth",

abstract = "Tuza (1981) conjectured that the cardinality τ(G) of a minimum set of edges that intersects every triangle of a graph G is at most twice the cardinality ν(G) of a maximum set of edge-disjoint triangles of G. I this paper we present three results regarding Tuza's Conjecture. We verify it for graphs with treewidth at most 6; and we show that τ(G)≤32ν(G) for every planar triangulation G different from K4; and that τ(G)≤95ν(G)+15 if G is a maximal graph with treewidth 3.",

keywords = "Triangle transversal, treewidth, triangle packing, triangulation",

author = "F. Botler and Fernandes, {C. G.} and J. Guti{\'e}rrez",

note = "Publisher Copyright: {\textcopyright} 2019 The Author(s).; 10th Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2019 ; Conference date: 02-06-2019 Through 07-06-2019",

year = "2019",

doi = "10.1016/j.entcs.2019.08.016",

language = "English",

volume = "346",

pages = "171--183",

journal = "Electronic Notes in Theoretical Computer Science",

issn = "1571-0661",

}

TY - JOUR

T1 - On Tuza's Conjecture for Triangulations and Graphs with Small Treewidth

AU - Botler, F.

AU - Fernandes, C. G.

AU - Gutiérrez, J.

PY - 2019

Y1 - 2019

N2 - Tuza (1981) conjectured that the cardinality τ(G) of a minimum set of edges that intersects every triangle of a graph G is at most twice the cardinality ν(G) of a maximum set of edge-disjoint triangles of G. I this paper we present three results regarding Tuza's Conjecture. We verify it for graphs with treewidth at most 6; and we show that τ(G)≤32ν(G) for every planar triangulation G different from K4; and that τ(G)≤95ν(G)+15 if G is a maximal graph with treewidth 3.

AB - Tuza (1981) conjectured that the cardinality τ(G) of a minimum set of edges that intersects every triangle of a graph G is at most twice the cardinality ν(G) of a maximum set of edge-disjoint triangles of G. I this paper we present three results regarding Tuza's Conjecture. We verify it for graphs with treewidth at most 6; and we show that τ(G)≤32ν(G) for every planar triangulation G different from K4; and that τ(G)≤95ν(G)+15 if G is a maximal graph with treewidth 3.

KW - Triangle transversal

KW - treewidth

KW - triangle packing

KW - triangulation

UR - http://www.scopus.com/inward/record.url?scp=85076255155&partnerID=8YFLogxK

U2 - 10.1016/j.entcs.2019.08.016

DO - 10.1016/j.entcs.2019.08.016

M3 - Conference article

AN - SCOPUS:85076255155

SN - 1571-0661

VL - 346

SP - 171

EP - 183

JO - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

T2 - 10th Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2019

Y2 - 2 June 2019 through 7 June 2019

ER -

On Tuza's Conjecture for Triangulations and Graphs with Small Treewidth

Resumen

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto