Packing and Covering Triangles in K 4-free Planar Graphs

Penny Haxell, Alexandr Kostochka, Stéphan Thomassé

Research output: Contribution to journalArticlepeer-review

Abstract

We show that every K 4-free planar graph with at most ν edge-disjoint triangles contains a set of at most 3/2 ν 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.

Original languageEnglish (US)
Pages (from-to)653-662
Number of pages10
JournalGraphs and Combinatorics
Volume28
Issue number5
DOIs
StatePublished - Sep 2012

Keywords

  • Planar
  • Triangle packing and covering
  • Tuza's conjecture

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Packing and Covering Triangles in K 4-free Planar Graphs'. Together they form a unique fingerprint.

Cite this