English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Tuza’s Conjecture asserts that the minimum number \(\tau _{\varDelta }'(G)\) of edges of a graph G whose deletion results in a triangle-free graph is at most 2 times the maximum number \(\nu _{\varDelta }'(G)\) of edge-disjoint triangles of G. The complete graphs \(K_{4}\) and \(K_{5}\) show that the constant 2 would be best possible. Moreover, if true, the conjecture would be essentially tight even for \(K_{4}\)-free graphs. In this paper, we consider several subclasses of \(K_{4}\)-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 \(\tau _{\varDelta }'(G)\) and \(\nu _{\varDelta }'(G)\) into an equivalent one for the clique cover number and the independence number of the triangle graph of G and we provide \(\theta \)-bounding functions for classes related to triangle graphs. In particular, we obtain optimal \(\theta \)-bounding functions for the classes \({\textit{Free}}(K_{5}, \text{ claw, } \text{ diamond })\) and \({\textit{Free}}(P_{5}, \text{ diamond }, K_{2,3})\) and a \(\chi \)-bounding function for the class \((\text{ banner, } \text{ odd-hole }, \overline{K_{1, 4}})\).

Triangle Packings and Transversals of Some $$K_{4}$$ K 4 -Free Graphs