Search

We show that every K 4-free planar graph with at most ν edge-disjoint triangles contains a set of at most $${\frac32\nu}$$ 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

Let @n(G) denote the maximum number of edge-disjoint triangles in a graph G and @t^*(G) denote the minimum total weight of a fractional covering of its triangles by edges. Krivelevich proved that @t^*(G)@[email protected](G) for every graph G. This is sharp, since for the complete graph K"4 we have @n(K"4)=1 and @t^*(K"4)=2. We refine this result by showing that if a graph G has @t^*(G)>[email protected](G)-x, then G contains @n(G)[email protected][email protected]? edge-disjoint K"4-subgraphs plus an additional @[email protected]? edge-disjoint triangles. Note that just these K"4's and triangles witness that @t^*(G)>[email protected](G)[email protected][email protected]?. Our proof also yields that @t^*(G)@[email protected](G) for each K"4-free graph G. In contrast, we show that for each @e>0, there exists a K"4-free graph G"@e such that @t(G"@e)>([email protected])@n(G"@e).