The path partition conjecture is true for claw-free graphs (Q878616): Difference between revisions

The detour order of a graph \(G\), denoted \(\tau(G)\), is the order of a longest path in \(G\). A 1983 conjecture states that if \(G\) is a graph and \((a,b)\) is a pair of positive integers such that \(\tau(G)= a+ b\), then the vertex set of \(G\) has a partition \((A,B)\) such that \(\tau(G(A))\leq a\) and \(\tau(G(B))\leq b\). This paper proves this conjecture for the class of claw-free graphs and it also shows that to prove this conjecture it is sufficient to consider the class of 2-connected graphs.