Packing and Covering Triangles in Planar Graphs |
| |
| Authors: | Qing Cui Penny Haxell Will Ma |
| |
| Institution: | 1. Department of Mathematics, Nanjing University of Aeronautics and Astronautics, 210016, Nanjing, People’s Republic of China
2. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, N2L 3G1, Canada
|
| |
| Abstract: | Tuza conjectured that if a simple graph G does not contain more than k pairwise edge-disjoint triangles, then there exists a set of at most 2k edges that meets all triangles in G. It has been shown that this conjecture is true for planar graphs and the bound is sharp. In this paper, we characterize the set of extremal planar graphs. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
