×

Packing and covering triangles in planar graphs. (English) Zbl 1205.05178

Summary: 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 that meets all triangles in \(G\). It has been shown that this conjecture is true for planar graphs and the bound is sharp. In this paper, we characterize the set of extremal planar graphs.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Haxell P.E.: Packing and covering triangles in graphs. Discrete Math. 195, 251–254 (1999) · Zbl 0930.05077 · doi:10.1016/S0012-365X(98)00183-6
[2] Haxell P.E., Kohayakawa Y.: Packing and covering triangles in tripartite graphs. Graphs Combin. 14, 1–10 (1998) · Zbl 0895.05048 · doi:10.1007/s003730050010
[3] Krivelevich M.: On a conjecture of Tuza about packing and covering of triangles. Discrete Math. 142, 281–286 (1995) · Zbl 0920.05056 · doi:10.1016/0012-365X(93)00228-W
[4] Tuza, Zs.: Conjecture, Finite and Infinite Sets (Eger, Hungary 1981). In: Hajnal, A., Lovász, L., Sós, V. T. (eds.) Proc. Colloq. Math. Soc. J. Bolyai, vol. 37, p. 888. North-Holland, Amsterdam (1984)
[5] Tuza Zs.: A conjecture on triangles of graphs. Graphs Combin. 6, 373–380 (1990) · Zbl 0724.05059 · doi:10.1007/BF01787705
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.