Abstract
We show that every K 4-free planar graph with at most ν edge-disjoint triangles contains a set of at most \({\frac32\nu}\) edges whose removal makes the graph triangle-free. Moreover, equality is attained only when G is the edge-disjoint union of 5-wheels plus possibly some edges that are not in triangles. We also show that the same statement is true if instead of planar graphs we consider the class of graphs in which each edge belongs to at most two triangles. In contrast, it is known that for any c < 2 there are K 4-free graphs with at most ν edge-disjoint triangles that need more than cν edges to cover all triangles.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aparna Lakshmanan, S., Bujtás, Cs., Tuza, Zs.: Small edge sets meeting all triangles of a graph (2011, submitted)
Chapuy, G., DeVos, M., McDonald, J., Mohar, B. Scheide, D.: Packing triangles in weighted graphs (2011, submitted)
Cui Q., Haxell P. E., Ma W.: Packing and covering triangles in planar graphs. Graphs Comb. 25, 817–824 (2009)
Fajtlowicz S.: On the size of independent sets in graphs. Congr. Numer. 21, 269–274 (1978)
Haxell P.: Packing and covering triangles in graphs. Discret. Math. 195, 251–254 (1999)
Haxell P., Kohayakawa Y.: Packing and covering triangles in tripartite graphs. Graphs Comb. 14, 1–10 (1998)
Haxell, P., Kostochka, A., Thomassé, S.: A stability theorem on fractional covering of triangles by edges. Eur. J. Comb. (2011, in press)
Krivelevich M.: On a conjecture of Tuza about packing and covering of triangles. Discrete Math 142, 281–286 (1995)
McKay, B.: Combinatorial data. http://cs.anu.edu.au/people/bdm/data/
Stanton W.: Some Ramsey-type numbers and the independence ratio. Trans. Am. Math. Soc. 256, 353–370 (1979)
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., pp. 888. North-Holland, Amsterdam (1984)
Tuza Zs.: A conjecture on triangles of graphs. Graphs Comb. 6, 373–380 (1990)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was done at the Institute for Pure and Applied Mathematics at UCLA. P. Haxell’s research was partially supported by NSERC. A. Kostochka’s research was supported in part by NSF grant DMS-0965587 and by grant 09-01-00244 of the Russian Foundation for Basic Research.
Rights and permissions
About this article
Cite this article
Haxell, P., Kostochka, A. & Thomassé, S. Packing and Covering Triangles in K 4-free Planar Graphs. Graphs and Combinatorics 28, 653–662 (2012). https://doi.org/10.1007/s00373-011-1071-9
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-011-1071-9