Packing and Covering Triangles in K 4-free Planar Graphs

Abstract : We show that every K 4-free planar graph with at most ν edge-disjoint triangles contains a set of at most 32ν 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.
Type de document :
Article dans une revue
Graphs and Combinatorics, Springer Verlag, 2012, 28 (5), pp.653-662. 〈10.1007/s00373-011-1071-9〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00806743
Contributeur : Alexandre Pinlou <>
Soumis le : mardi 2 avril 2013 - 11:44:22
Dernière modification le : mardi 24 avril 2018 - 13:52:42

Lien texte intégral

Identifiants

Collections

Citation

Penny Haxell, Alexandr Kostochka, Stéphan Thomassé. Packing and Covering Triangles in K 4-free Planar Graphs. Graphs and Combinatorics, Springer Verlag, 2012, 28 (5), pp.653-662. 〈10.1007/s00373-011-1071-9〉. 〈lirmm-00806743〉

Partager

Métriques

Consultations de la notice

305