Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423446 | Discrete Mathematics | 2012 | 8 Pages |
Abstract
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.The conjecture was proved by Faudree et al. with the additional condition that G has at most 65nâ2 edges. In this paper, for each integer kâ¥3, we prove that every non-star graph with girth at least 5 and at most 2kâ1knâαk(n) edges is packable, where αk(n) is o(n) for every k. This implies that the conjecture is true for sufficiently large planar graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Agnieszka Görlich, Andrzej Å»ak,