Abstract | ||
---|---|---|
It is shown that if G is a tripartite graph such that the maximum size of a set of pairwise edge-disjoint triangles is $\nu (G)$, then there is a set C of edges of G of size at most $(2 - \varepsilon )\nu (G)$, such that $E(T) \cap C \not= \emptyset $ for every triangle T of G, where $\varepsilon > 0.044$. This improves the previous bound of $(7/3)\nu (G)$ due to Tuza [6]. |
Year | DOI | Venue |
---|---|---|
1998 | 10.1007/s003730050010 | Graphs and Combinatorics |
Keywords | Field | DocType |
tuza's conjecture the first author was partially supported by nserc. the second author was partially sup- ported by cnpq proc. 300334/93-1 and protem-cc-ii project procomb,triangles,covering,tripartite graphs,. packing | Pairwise comparison,Topology,Discrete mathematics,Graph,Combinatorics,Mathematics | Journal |
Volume | Issue | ISSN |
14 | 1 | 0911-0119 |
Citations | PageRank | References |
8 | 0.91 | 2 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
P. E. Haxell | 1 | 212 | 26.40 |
Yoshiharu Kohayakawa | 2 | 172 | 22.74 |