A new approach to the path partition conjecture

Abstract

The detour order of G, denoted by τ(G), is the order of a longest path in G. A partition (A, B) of V(G) such that r(〈A〉) ≤ a and τ((B)) ≤ b is called an (a, b)-partition. The Path Partition Conjecture is that given a pair of positive integers a, b and a graph G such that τ(G) = a + b, then G has an (a, b)-partition. A graph G having an (a, b)-partition is called (a, b)-exact if τ(G) = a + b and every (a, b)-partition (A, B) of G satisfies τ(〈A〉) = a and τ(〈B〉) = b. We prove that there exists a noncomplete traceable (a, b)-exact graph for every pair of integers a, b ≥ 3. The detour deficiency of G is defined as p(G) := v(G) - τ(G). A graph with detour deficiency p is called p-deficient. We investigate the path partition function f : ℤ⁺ ∪ {0} → ℤ, defined by: f(p) is the greatest integer for which every connected p-deficient graph G has an (a, b)-partition for every pair a, b such that a + b = τ(G) - f(p).