TY - JOUR
T1 - A stability theorem on fractional covering of triangles by edges
AU - Haxell, Penny
AU - Kostochka, Alexandr
AU - Thomassé, Stéphan
N1 - Funding Information:
The first author’s research was partially supported by NSERC . The research of the second author was supported in part by NSF grants DMS-06-50784 and DMS-0965587 and by grant 08-01-00673 from the Russian Foundation for Basic Research .
PY - 2012/7
Y1 - 2012/7
N2 - 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 ε).
AB - 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 ε).
UR - http://www.scopus.com/inward/record.url?scp=84856973198&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84856973198&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2011.09.024
DO - 10.1016/j.ejc.2011.09.024
M3 - Article
AN - SCOPUS:84856973198
SN - 0195-6698
VL - 33
SP - 799
EP - 806
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
IS - 5
ER -