Triangle Packings and Transversals of Some K_4-Free Graphs

Research output: Contribution to journalArticle

104 Downloads (Pure)

Abstract

Tuza’s Conjecture asserts that the minimum number τ′Δ(G) of edges of a graph G whose deletion results in a triangle-free graph is at most 2 times the maximum number ν′Δ(G) of edge-disjoint triangles of G. The complete graphs K4 and K5 show that the constant 2 would be best possible. Moreover, if true, the conjecture would be essentially tight even for K4 -free graphs. In this paper, we consider several subclasses of K4 -free graphs. We show that the constant 2 can be improved for them and we try to provide the optimal one. The classes we consider are of two kinds: graphs with edges in few triangles and graphs obtained by forbidding certain odd-wheels. We translate an approximate min-max relation for τ′Δ(G) and ν′Δ(G) into an equivalent one for the clique cover number and the independence number of the triangle graph of G and we provide θ -bounding functions for classes related to triangle graphs. In particular, we obtain optimal θ -bounding functions for the classes Free(K5, claw, diamond ) and Free(P5, diamond ,K2,3) and a χ -bounding function for the class ( banner, odd-hole ,K1,4¯¯¯¯¯¯¯¯¯) .
Original languageEnglish
Pages (from-to)647-668
JournalGraphs and Combinatorics
Volume34
Issue number4
Early online date19 May 2018
DOIs
Publication statusPublished - 01 Jul 2018

Keywords

  • Triangle graphs
  • Triangle packing and transversal
  • χ-Bounded

Fingerprint Dive into the research topics of 'Triangle Packings and Transversals of Some K_4-Free Graphs'. Together they form a unique fingerprint.

  • Cite this