Small Edge Sets Meeting all Triangles of a Graph
Tóm tắt
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.
Tài liệu tham khảo
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)