ON A CONJECTURE OF TUZA ABOUT PACKING AND COVERING OF TRIANGLES

被引：56

作者：

KRIVELEVICH, M ^{[1
]}

机构：

[1] TECHNION ISRAEL INST TECHNOL,DEPT MATH,IL-32000 HAIFA,ISRAEL

来源：

DISCRETE MATHEMATICS | 1995年 / 142卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(93)00228-W

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Zs. Tuza conjectured that if a simple graph G does not contain more than k pairwise edge disjoint triangles, then there exists a set of at most 2k edges which meets all triangles in G. We prove this conjecture for K-3,K-3-free graphs (graphs that do not contain a homeomorph of K-3,K-3). Two fractional versions of the conjecture are also proved.

引用

页码：281 / 286

页数：6

共 6 条

[1] AN APPROACH TO THE SUBGRAPH HOMEOMORPHISM PROBLEM [J].

ASANO, T .

THEORETICAL COMPUTER SCIENCE, 1985, 38 (2-3) :249-267

[2] MATCHINGS AND COVERS IN HYPERGRAPHS [J].

FUREDI, Z .

GRAPHS AND COMBINATORICS, 1988, 4 (02) :115-206

[3] MAXIMUM DEGREE AND FRACTIONAL MATCHINGS IN UNIFORM HYPERGRAPHS [J].

FUREDI, Z .

COMBINATORICA, 1981, 1 (02) :155-162

[4]

HALL DW, 1943, B AM MATH SOC, V49, P935, DOI DOI 10.1090/S0002-9904-1943-08065-2

[5] A CONJECTURE ON TRIANGLES OF GRAPHS [J].

TUZA, Z .

GRAPHS AND COMBINATORICS, 1990, 6 (04) :373-380

[6]

Tuza Z, 1981, FINITE INFINITE SETS, P888

← 1 →