A stability theorem on fractional covering of triangles by edges

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 K4 we have ν(K4)=1 and τ∗(K4)=2. We refine this result by showing that if a graph G has τ∗(G)≥2ν(G)−x, then G contains ν(G)−⌊10x⌋ edge-disjoint K4-subgraphs plus an additional ⌊10x⌋ edge-disjoint triangles. Note that just these K4's and triangles witness that τ∗(G)≥2ν(G)−⌊10x⌋. Our proof also yields that τ∗(G)≤1.8ν(G) for each K4-free graph G. In contrast, we show that for each ϵ>0, there exists a K4-free graph Gϵ such that τ(Gϵ)>(2−ϵ)ν(Gϵ).
Type de document :
Article dans une revue
European Journal of Combinatorics, Elsevier, 2012, 33 (5), pp.799-806. 〈10.1016/j.ejc.2011.09.024〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00806759
Contributeur : Alexandre Pinlou <>
Soumis le : mardi 2 avril 2013 - 11:57:48
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Collections

Citation

Penny Haxell, Alexandr Kostochka, Stéphan Thomassé. A stability theorem on fractional covering of triangles by edges. European Journal of Combinatorics, Elsevier, 2012, 33 (5), pp.799-806. 〈10.1016/j.ejc.2011.09.024〉. 〈lirmm-00806759〉

Partager

Métriques

Consultations de la notice

186