Path partitions and \(P_{n}\)-free sets (Q1763347)

The detour order \(\tau(G)\) of a graph \(G\) is the number of vertices of a longest path of \(G\). If \(S\) is a subset of vertices of a graph \(G\) such that the graph induced by \(S\) has detour order at most \(n\), then \(S\) is called a \(P_{n+1}\)-free set in \(G\). The path partition conjecture can be stated as follows: For any graph \(G\) and any positive integer \(n<\tau(G)\), there exists a \(P_{n+1}\)-free set \(S\) in \(G\) such that \(\tau(G-S)\leq\tau(G)-n\). In Theorem 2.1 the authors prove: Let \(G\) be a graph and \(n\) an integer with \(2\leq n<\tau(G)\). If \(X\) is a maximal \(P_{n+1}\)-free set in \(G\), then \(\tau(G-X)\leq\tau(G)-\frac{2}{3}(n+1)\). In addition, they show that if the graph \(G\) has no cycle of length less than \(n\) or greater than \(\tau(G)-n+2\), then \(\tau(G-X)\leq\tau(G)-n\) for every maximal \(P_{n+1}\)-free set in \(G\). As a corollary of the latter result, the authors prove the path partition conjecture for the special class of connected and weakly pancyclic graphs.