Dense graphs with a large triangle cover have a large triangle packing

Details Dense graphs with a large triangle cover have a large triangle packing Dense graphs with a large triangle cover have a large triangle packing

2010-09-02

arxiv.org/abs/1009.0353v1

Mathematics

Combinatorics

Scientific paper

It is well known that a graph with $m$ edges can be made triangle-free by removing (slightly less than) $m/2$ edges. On the other hand, there are many classes of graphs which are hard to make triangle-free in the sense that it is necessary to remove roughly $m/2$ edges in order to eliminate all triangles. It is proved that dense graphs that are hard to make triangle-free, have a large packing of pairwise edge-disjoint triangles. In particular, they have more than $m(1/4+c\beta^2)$ pairwise edge-disjoint triangles where $\beta$ is the density of the graph and $c$ is an absolute constant. This improves upon a previous $m(1/4-o(1))$ bound which follows from the asymptotic validity of Tuza's conjecture for dense graphs. It is conjectured that such graphs have an asymptotically optimal triangle packing of size $m(1/3-o(1))$. The result is extended to larger cliques and odd cycles.

Affiliated with

Also associated with

No associations

Rating

Dense graphs with a large triangle cover have a large triangle packing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dense graphs with a large triangle cover have a large triangle packing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dense graphs with a large triangle cover have a large triangle packing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-375661