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

被引：3

作者：

Botler, F. ^{[1
]}

Fernandes, C. G. ^{[2
]}

Gutierrez, J. ^{[2
]}

机构：

[1] Univ Fed Rio de Janeiro, Programa Engn Sistemas & Comp, Rio De Janeiro, Brazil

[2] Univ Sao Paulo, Dept Ciencia Comp, Sao Paulo, Brazil

来源：

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE | 2019年 / 346卷

基金：

巴西圣保罗研究基金会;

关键词：

Triangle transversal; triangle packing; treewidth; triangulation; COVERING TRIANGLES; PACKING;

D O I：

10.1016/j.entcs.2019.08.016

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Tuza (1981) conjectured that the cardinality tau(G) of a minimum set of edges that intersects every triangle of a graph G is at most twice the cardinality nu(G) of a maximum set of edge-disjoint triangles of G. In this paper we present three results regarding Tuza's Conjecture. We verify it for graphs with treewidth at most 6; and we show that tau(G) <= 3/2 nu(G) for every planar triangulation G different from K-4; and that tau(G) <= 9/5 nu(G) + 1/5 if G is a maximal graph with treewidth 3.

引用

页码：171 / 183

页数：13

共 15 条

[1] Tuza's Conjecture is Asymptotically Tight for Dense Graphs
Baron, Jacob D.
Kahn, Jeff
[J]. COMBINATORICS PROBABILITY & COMPUTING, 2016, 25 (05) : 645 - 667
[2] A partial k-arboretum of graphs with bounded treewidth
Bodlaender, HL
[J]. THEORETICAL COMPUTER SCIENCE, 1998, 209 (1-2) : 1 - 45
[3] Bondy U. S. R., 2008, Graph theory
[4] On colouring the nodes of a network
Brooks, RL
[J]. PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1941, 37 : 194 - 197
[5] Sufficient Conditions for Tuza's Conjecture on Packing and Covering Triangles
Chen, Xujin
Diao, Zhuo
Hu, Xiaodong
Tang, Zhongzheng
[J]. Combinatorial Algorithms, 2016, 9843 : 266 - 277
[6] Packing and Covering Triangles in Planar Graphs
Cui, Qing
Haxell, Penny
Ma, Will
[J]. GRAPHS AND COMBINATORICS, 2009, 25 (06) : 817 - 824
[7] Gross JL, 2014, ARS MATH CONTEMP, V7, P379
[8] Packing and covering triangles in graphs
Haxell, PE
[J]. DISCRETE MATHEMATICS, 1999, 195 (1-3) : 251 - 254
[9] Packing and covering triangles in tripartite graphs
Haxell, PE
Kohayakawa, Y
[J]. GRAPHS AND COMBINATORICS, 1998, 14 (01) : 1 - 10
[10] Packing and Covering Triangles in K 4-free Planar Graphs
Haxell, Penny
Kostochka, Alexandr
Thomasse, Stephan
[J]. GRAPHS AND COMBINATORICS, 2012, 28 (05) : 653 - 662

← 1 2 →