Packing And Covering Triangles In (K₄,W₄)-Free Graphs

Let G be a simple graph.We say that a family A of triangles in G is a triangle packing of G if the elements of A are pairwise edge-disjoint.It is referred to as independent family of triangles of G.A set E'(?)E(G)of edges of G is called a triangle covering if E' ? E[T]?(?) for each triangles T of G.It is referred to as a transversal for G.We denote by v(G)the maximum cardinality of an independent family of triangles in G,and by ?(G)the minimum cardinality of a transversal for G.In this thesis,we consider an elegant conjecture of Tuza,first raised in 1984[10],which states that ?(G)?2v(G)for every graph G.Some partial results on this conjecture have been obtained for certain special classes of graphs.In[11],Tuza showed that the conjecture is true for planar graphs,K5-free chordal graphs,and graphs with n vertices and at least 7n2/16 edges.More recently,Lakshmanan,Bujtas,and Tuza[9]showed that graphs G without odd-wheel satisfy the conjecture.Haxell[4]showed that ?(G)?66/23v(G)for any graphs.In this thesis,we study the problem of packing and covering triangles in(K4,W4)-free graphs.First,we choose a maximum independent family of triangles B,then fix a maximum independent family of triangles B1 in the family of trian-gles(B,1)of which each elements T satisfies |E[T]? E|B]|=1.Accordingly,in the set B there exists a set F corresponding to B1,let the set of edges where B1 and F intersect be denoted as {e(T):T?B1}.Then we can prove that C=E[B\F ? {e(T):T?B1} is a transversal of graph G and get Lemma 1 that?(G)?(3-2?)v(G)Then let G' denote the graph obtained by deleting all edges of {e(T):T ?B1},and make it an odd-wheel-free graph by deleting some edges.According to Lemma 3 that ?(G)?2v(G)for any odd-wheel-free graphs.We can get Lemma 4 that(?)By combining Lemma 1 and Lemma 4 we can show Theorem 5 that ?(G)?31/11v(G)for any(K4,W4)-free graphs.