Abstract
It was conjectured in 1981 by the third author that if a graph G does not contain more than t pairwise edge-disjoint triangles, then there exists a set of at most 2t edges that shares an edge with each triangle of G. In this paper, we prove this conjecture for odd-wheel-free graphs and for ‘triangle-3-colorable’ graphs, where the latter property means that the edges of the graph can be colored with three colors in such a way that each triangle receives three distinct colors on its edges. Among the consequences we obtain that the conjecture holds for every graph with chromatic number at most four. Also, two subclasses of K 4-free graphs are identified, in which the maximum number of pairwise edge-disjoint triangles is equal to the minimum number of edges covering all triangles. In addition, we prove that the recognition problem of triangle-3-colorable graphs is intractable.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aharoni R.: Ryser’s conjecture for tripartite 3-graphs. Combinatorica 21, 1–4 (2001)
Lakshmanan, S. Aparna, Bujtás, Cs., Tuza, Zs.: manuscript in preparation
Bagga J.: Old and new generalizations of line graphs. Int. J. Math. Math. Sci 29, 1509–1521 (2004)
Chapuy, G., DeVos, M., McDonald, J., Mohar, B., Scheide, D.: Packing triangles in weighted graphs (2010)
Chudnovsky M., Robertson N., Seymour P., Thomas R.: The strong perfect graph theorem. Ann. Math. 164, 51–229 (2006)
Cui Q., Haxell P., Ma W.: Packing and covering triangles in planar graphs. Graphs Combin. 25, 817–824 (2009)
Erdős P., Gallai T., Tuza Zs.: Covering and independence in triangle structures. Discret. Math. 150, 89–101 (1996)
Haxell P.E.: Packing and covering triangles in graphs. Discret. Math. 195, 251–254 (1999)
Haxell P.E., Kohayakawa Y.: Packing and covering triangles in tripartite graphs. Graphs Combin. 14, 1–10 (1998)
Haxell, P., Kostochka, A., Thomassé, S.: A stability theorem on fractional covering of triangles by edges (2010)
Holyer I.: The NP-completeness of edge-colouring. SIAM J. Comput. 10, 718–720 (1981)
Krivelevich M.: On a conjecture of Tuza about packing and covering of triangles. Discret. Math. 142, 281–286 (1995)
Le V.B.: Gallai graphs and anti-Gallai graphs. Discret. Math. 159, 179–189 (1996)
Mansour T., Song C., Yuster R.: A comment on Ryser’s conjecture for intersecting hypergraphs. Graphs Combin. 25, 101–109 (2009)
Prisner E.: Intersection multigraphs of uniform hypergraphs. Graphs Combin. 14, 363–375 (1998)
Tuza, Zs.: Conjecture, finite and infinite sets. In: Hajnal, A., Lovász, L., Sós, V.T. (eds.) Proc. Colloq. Math. Soc. J. Bolyai (Eger, Hungary, 1981), vol. 37, p. 888, North-Holland, Amsterdam (1984)
Tuza Zs.: Ryser’s conjecture on transversals of r-partite hypergraphs. Ars Combin. 16B, 201–209 (1983)
Tuza Zs.: A conjecture on triangles of graphs. Graphs Combin. 6, 373–380 (1990)
Tuza, Zs.: Some open problems on colorings and coverings of graphs (Abstract), Graphentheorie-Tagung Oberwolfach (1990)
Tuza Zs.: Perfect triangle families. Bull. Lond. Math. Soc. 26, 321–324 (1994)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported in part by the Hungarian Scientific Research Fund, OTKA grant 81493.
Rights and permissions
About this article
Cite this article
Aparna Lakshmanan, S., Bujtás, C. & Tuza, Z. Small Edge Sets Meeting all Triangles of a Graph. Graphs and Combinatorics 28, 381–392 (2012). https://doi.org/10.1007/s00373-011-1048-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-011-1048-8