A Note on Packing Graphs Without Cycles of Length up to Five

Agnieszka Görlich, Andrzej Żak

Abstract


The following statement was conjectured by Faudree, Rousseau, Schelp and Schuster: if a graph $G$ is a non-star graph without cycles of length $m \leq 4$ then $G$ is a subgraph of its complement. So far the best result concerning this conjecture is that every non-star graph $G$ without cycles of length $m \leq 6$ is a subgraph of its complement. In this note we show that $m\leq 6$ can be replaced by $m \leq 5$.


Full Text: PDF