Name
Abstract | ||
|---|---|---|
We show that every K (4)-free planar graph with at most nu edge-disjoint triangles contains a set of at most edges whose removal makes the graph triangle-free. Moreover, equality is attained only when G is the edge-disjoint union of 5-wheels plus possibly some edges that are not in triangles. We also show that the same statement is true if instead of planar graphs we consider the class of graphs in which each edge belongs to at most two triangles. In contrast, it is known that for any c < 2 there are K (4)-free graphs with at most nu edge-disjoint triangles that need more than c nu edges to cover all triangles. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s00373-011-1071-9 | GRAPHS AND COMBINATORICS |
Keywords | Field | DocType |
Triangle packing and covering,Planar,Tuza's conjecture | Topology,Graph,Combinatorics,CPCTC,Planar,Nested triangles graph,Mathematics,Planar graph | Journal |
Volume | Issue | ISSN |
28 | 5 | 0911-0119 |
Citations | PageRank | References |
1 | 0.37 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Penny E. Haxell | 1 | 130 | 16.64 |
| Alexandr V. Kostochka | 2 | 682 | 89.87 |
| Stéphan Thomassé | 3 | 651 | 66.03 |