Packing and Covering Triangles in K 4-free Planar Graphs

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 al...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2012-09, Vol.28 (5), p.653-662
Main Authors: Haxell, Penny, Kostochka, Alexandr, Thomassé, Stéphan
Format: Article
Language:English
Subjects:
Computer Science
Discrete Mathematics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-011-1071-9