Sparse graphs of girth at least five are packable
A graph \(G\) of order \(n\) is packable if it is a subgraph of its complement. \textit{R. J. Faudree}, \textit{C. C. Rousseau}, \textit{R. H. Schelp}, and \textit{S. Schuster} [Czech. Math. J. 31(106), 53--62 (1981; Zbl 0479.05028)] conjectured that every non-star graph of girth at least five is packable. They proved it for graphs with at most \(\frac{6}{5}n-2\) edges. In the paper under review it is proved that the conjecture is true also when \(G\) has at most \(\frac{2k-1}{k}n-\alpha_k(n)\) edges, where \(k \geq 3\) and \(\alpha_k(n)\) is \(o(n)\) for every \(k\). This implies that the conjecture is true for sufficiently large planar graphs.
- A note on embedding graphs without short cycles
- A note on packing graphs without cycles of length up to five
- Edge disjoint placement of graphs
- Embedding (p,p - 1) graphs in their complements
- Embedding graphs in their complements
- Every (p,p-2) graph is contained in its complement
- Fixed-point-free embeddings of graphs in their complements
- scientific article; zbMATH DE number 426373 (Why is no real title available?)
- scientific article; zbMATH DE number 861401 (Why is no real title available?)
- On packable digraphs
- Packings of graphs and applications to computational complexity
This page was built for publication: Sparse graphs of girth at least five are packable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1759402)
