Decomposing Graphs into Long Paths

Author: Kostochka Alexandr   Tashkinov Vladimir  

Publisher: Springer Publishing Company

ISSN: 0167-8094

Source: Order, Vol.20, Iss.3, 2003-01, pp. : 239-253

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

It is known that the edge set of a 2-edge-connected 3-regular graph can be decomposed into paths of length 3. W. Li asked whether the edge set of every 2-edge-connected graph can be decomposed into paths of length at least 3. The graphs C3, C4, C5, and K4e have no such decompositions. We construct an infinite sequence {Fi}i=0 of nondecomposable graphs. On the other hand, we prove that every other 2-edge-connected graph has a desired decomposition.