A proof of the two-path conjecture

MaRDI QIDQ5960794zbMATH OpenFDO

Authors Herbert Fleischner, Robert R. Molina, Ken W. Smith, Douglas B. West

Publication date 25 April 2002

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/122309, http://www.emis.de/journals/EJC/Volume_9/Abstracts/v9i1n4.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

connected graphpath

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

The authors prove the following result: If a graph \(G\) decomposes into two paths \(X\) and \(Y\), each of length \(n\) with \(n\geq 2\), and \(X\) and \(Y\) have at least one common vertex, then \(G\) has a path of length \(n\) distinct from \(X\) and \(Y\).

Recommendations

• A proof of the square paths conjecture
• The proofs of two directed paths conjectures of Bollobás and Leader
• The Path Partition Conjecture
• Proof of Ira Gessel's lattice path conjecture
• Proof of Berge's strong path partition conjecture for \(k=2\)
• The Erdős-Hajnal conjecture for paths and antipaths
• A Cantor-Bernstein Theorem for Paths in Graphs
• The directed path partition conjecture
• A human proof of Gessel's lattice path conjecture
• An Erdős-Ko-Rado theorem for unions of length 2 paths

Cited in

(6)

• On the Euclidean two paths problem
• Double paths
• A human proof of Gessel's lattice path conjecture
• scientific article; zbMATH DE number 845482 (Why is no real title available?)
• Decompositions into two paths
• Packing paths in complete graphs

This page was built for publication: A proof of the two-path conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5960794)