A stability theorem on fractional covering of triangles by edges

Penny Haxell, Alexandr Kostochka, Stéphan Thomassé

Research output: Contribution to journalArticlepeer-review

Abstract

Let ν(G) denote the maximum number of edge-disjoint triangles in a graph G and τ *(G) denote the minimum total weight of a fractional covering of its triangles by edges. Krivelevich proved that τ *(G)≤2ν(G) for every graph G. This is sharp, since for the complete graph K 4 we have ν(K 4)=1 and τ *(K 4)=2. We refine this result by showing that if a graph G has τ *(G)ge2ν(G)-x, then G contains ν(G)-⌊10x⌋ edge-disjoint K 4-subgraphs plus an additional ⌊10x⌋ edge-disjoint triangles. Note that just these K 4's and triangles witness that τ *(G)ge2ν(G)-⌊10x⌋ Our proof also yields that τ *(G)≤1.8ν(G) for each K 4-free graph G. In contrast, we show that for each ε>0, there exists a K 4-free graph G ε such that τ(G ε)>(2-ε)ν(G ε).

Original languageEnglish (US)
Pages (from-to)799-806
Number of pages8
JournalEuropean Journal of Combinatorics
Volume33
Issue number5
DOIs
StatePublished - Jul 2012

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'A stability theorem on fractional covering of triangles by edges'. Together they form a unique fingerprint.

Cite this