Skip to main content
Log in

Packing and Covering Triangles in K 4-free Planar Graphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

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 edges to cover all triangles.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aparna Lakshmanan, S., Bujtás, Cs., Tuza, Zs.: Small edge sets meeting all triangles of a graph (2011, submitted)

  2. Chapuy, G., DeVos, M., McDonald, J., Mohar, B. Scheide, D.: Packing triangles in weighted graphs (2011, submitted)

  3. Cui Q., Haxell P. E., Ma W.: Packing and covering triangles in planar graphs. Graphs Comb. 25, 817–824 (2009)

    Article  MATH  Google Scholar 

  4. Fajtlowicz S.: On the size of independent sets in graphs. Congr. Numer. 21, 269–274 (1978)

    MathSciNet  Google Scholar 

  5. Haxell P.: Packing and covering triangles in graphs. Discret. Math. 195, 251–254 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  6. Haxell P., Kohayakawa Y.: Packing and covering triangles in tripartite graphs. Graphs Comb. 14, 1–10 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  7. Haxell, P., Kostochka, A., Thomassé, S.: A stability theorem on fractional covering of triangles by edges. Eur. J. Comb. (2011, in press)

  8. Krivelevich M.: On a conjecture of Tuza about packing and covering of triangles. Discrete Math 142, 281–286 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  9. McKay, B.: Combinatorial data. http://cs.anu.edu.au/people/bdm/data/

  10. Stanton W.: Some Ramsey-type numbers and the independence ratio. Trans. Am. Math. Soc. 256, 353–370 (1979)

    Article  Google Scholar 

  11. 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)

    Google Scholar 

  12. Tuza Zs.: A conjecture on triangles of graphs. Graphs Comb. 6, 373–380 (1990)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Penny Haxell.

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

Reprints 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

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-011-1071-9

Keywords

Navigation