Sparse graphs of girth at least five are packable

作者：Goerlich Agnieszka; Zak Andrzej^*

来源：Discrete Mathematics, 2012, 312(24): 3606-3613.

DOI：10.1016/j.disc.2012.08.014

• Packing graphs
• Small cycles
• Planar graphs

A graph is packable if it is a subgraph of its complement. The following statement was conjectured by Faudree, Rousseau, Schelp and Schuster in 1981: every non-star graph G with girth at least 5 is packable. %26lt;br%26gt;The conjecture was proved by Faudree et al. with the additional condition that G has at most 6/5n - 2 edges. In this paper, for each integer k %26gt;= 3, we prove that every non-star graph with girth at least 5 and at most 2k-1/kn - alpha(k)(n) edges is packable, where alpha(k)(n) is o(n) for every k. This implies that the conjecture is true for sufficiently large planar graphs.

• 出版日期2012-12-28