Institutional Repository

An asymptotic result for the Path Partition Conjecture

Show simple item record

dc.contributor.author Frick M. en
dc.contributor.author Schiermeyer I. en
dc.date.accessioned 2012-11-01T16:31:35Z
dc.date.available 2012-11-01T16:31:35Z
dc.date.issued 2005 en
dc.identifier.citation Electronic Journal of Combinatorics en
dc.identifier.citation 12 en
dc.identifier.citation 1 R en
dc.identifier.citation 10 en
dc.identifier.issn 10778926 en
dc.identifier.uri http://hdl.handle.net/10500/7387
dc.description.abstract The detour order of a graph G, denoted by τ (G), is the order of a longest path in G. A partition of the vertex set of G into two sets, A and B, such that τ((A)) ≤ a and τ(〈B〉) ≤ b is called an (a, b)-partition of G. If G has an (a, b)-partition for every pair (a, b) of positive integers such that a + b = τ(G), then we say that G is τ-partitionable. The Path Partition Conjecture (PPC), which was discussed by Lovász and Mihók in 1981 in Szeged, is that every graph is τ-partitionable. It is known that a graph G of order n and detour order τ = n -p is τ-partitionable if p = 0, 1. We show that this is also true for p = 2, 3, and for all p ≥ 4 provided that n≥p(10p-3). en
dc.language.iso en en
dc.title An asymptotic result for the Path Partition Conjecture en
dc.type Article en


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search UnisaIR


Browse

My Account

Statistics