Partitioning a Graph into Two Square-Cycles

Genghua Fan, Henry Kierstead

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


A square-cycle is the graph obtained from a cycle by joining every pair of vertices of distance two in the cycle. The length of a square-cycle is the number of vertices in it. Let G be a graph on n vertices with minimum degree at least 2/3n and let c be the maximum length of a square-cycle in G. Pósa and Seymour conjectured that c = n. In this paper, it is proved that either c = n or 1/2n ≤ c ≤ 2/3n. As an application of this result, it is shown that G has two vertex-disjoint square-cycles C1 and C2 such that V(G) = V(C1) ∪ V(C2).

Original languageEnglish (US)
Pages (from-to)241-256
Number of pages16
JournalJournal of Graph Theory
Issue number3
StatePublished - Nov 1996

ASJC Scopus subject areas

  • Geometry and Topology


Dive into the research topics of 'Partitioning a Graph into Two Square-Cycles'. Together they form a unique fingerprint.

Cite this