The Path Partition Conjecture

Abstract

The Path Partition Conjecture (PPC) states that if G is any graph and (a, b) any pair of positive integers such that G has no path with more than a + b vertices, then there exists a partition (A, B) of the vertex set of G such that A has no path with more than a vertices, and B has no path with more than b vertices. We present a brief history of the PPC, discuss its relation to other conjectures and examine results supporting the PPC that have appeared in the literature since its first formulation in 1981. We conclude with a few related open problems.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 It Must Surely Be True…

Some conjectures are built, creating a ‘next step’ in an evolving body of work. Others are borrowed by changing some condition in an old respected conjecture that’s too hard to prove just now. Another type of conjecture is the type that arises almost organically, sprouting at different places on the globe from phrases like “it must surely be true that….”. The Path Partition Conjecture (PPC) is of the third type. You can easily explain this intriguing conjecture to your grandchildren or to the stranger seated next to you on the plane, by stating it as follows.

If G is a graph containing no path with more than τ vertices and a and b are two positive integers whose sum equals τ, then we can colour all the vertices of G, using only the colours amber and blue, in such a way that no path in G has more than a consecutive amber vertices or more than b consecutive blue vertices.

If you check the validity of the PPC for some specific graphs, you will most probably find that in each case it is easy to spot a colouring that will do the trick. In some cases you might even end up with fewer than a consecutive amber vertices and fewer than b consecutive blue ones. However, we still do not know whether this 37-year-old conjecture holds for all graphs.

If you google ‘Path Partition Conjecture’ you will find that several graph theorists have contributed results that lend support to the PPC and you are bound to stumble on a paper in Arxiv which contains an obviously false ‘proof’ of the PPC.

This chapter outlines the details of our seemingly never-ending journey toward settling the PPC. We also venture into unexplored territory to look at some new conjectures and problems that have occurred in various detours along the way. The most significant discoveries of our journey are presented here. We briefly illustrate the techniques that were used, by providing only the main steps of the proofs of our results.

2 Beginnings

A path with k vertices is denoted by P _k, and the detour order τ(G) of a graph G is the number of vertices on any longest path of G. (Since the PPC concerns vertex partitions, we prefer counting vertices, rather than edges in paths.) If S is any subset of the vertex set V (G) of a graph G, we denote by G[S] the subgraph of G induced by S. We call S a P _k -free set in G if τ(G[S]) < k.

In the early 90s, MF began working on a project to set up a framework for studying generalized colourings linked to different graph invariants. She defined, for a given graph invariant γ, an (m, k)^γ-colouring of a graph G as a partition of the vertex set of G into m subsets V ₁, …, V _m such that γ(G[V _i]) ≤ k for i = 1, …, m. The kth γ-chromatic number $\chi ^{\gamma }_k(G)$ of G is the minimum m for which G has an (m, k)^γ-colouring. The project was inspired by the pioneering paper [11] on τ-chromatic colourings by Chartrand, Geller and Hedetniemi. Their Theorem 2 gives an upper bound on the kth τ-chromatic number, depending only on k and τ.

Theorem 2.1 ([11])

$\chi _k^{\tau }(G)\leq \lfloor \frac {1}{2} (\tau (G)-k)\rfloor +2$ for every graph G and every k ≥ 3.

The Lovász Partition Theorem (Theorem 1 in [25]) yields an upper bound for the kth Δ-chromatic number (where Δ denotes maximum degree), depending only on k and Δ.

Theorem 2.2 ([25])

$\chi _k^{\Delta (G)}\leq \lceil \frac {\Delta (G)+1}{k+1}\rceil$ for every graph G and every k ≥ 0.

Lick and White [24] established an analogous upper bound for the kth ρ-chromatic number (where ρ(G), the degeneracy of G, is the maximum of the minimum degrees of the induced subgraphs of G.)

Theorem 2.3 ([24])

$\chi _k^{\rho (G)}\leq \lceil \frac {\rho (G)+1}{k+1}\rceil$ for every graph G and every k ≥ 0.

Note that

$$\displaystyle \begin{aligned}\chi^{\tau}_1 = \chi^{\Delta}_0 = \chi^{\rho}_0=\chi (G),\end{aligned}$$

where χ(G) denotes the ordinary chromatic number.

It is not unreasonable to expect that the bound in Theorem 2.1 could be reduced to be more in line with Theorems 2.2 and 2.3. To prove Theorem 2.1, Chartrand et al. considered a P _k+1-free set M of maximum order in G. They observed that every vertex in G − M (in particular, each end-vertex of a longest path in G − M) is adjacent to a vertex in M. From this they deduced that τ(G − M) ≤ τ(G) − 2 and their result followed by induction on the detour order. MF noticed that by the maximality of M, every vertex in G − M (in particular, an end-vertex of a longest path in G − M) is actually adjacent to an end-vertex of a path of order at least k∕2 in M. This implies that τ(G − M) ≤ τ(G) − k∕2. By using this stronger result in the induction argument, it can be shown that $\chi _k^{\tau }(G)\leq \frac {2\tau (G)}{k}$ for every graph G and every k ≥ 1. MF then thought that it would be easy to take this a step further and prove that $\chi _k^{\tau }(G)\leq \frac {\tau (G)}{k}$ for all k ≥ 1. This would be a nice extension of the classic theorem of Gallai [17] that χ(G) ≤ τ(G) and it would be similar to Theorems 2.2 and 2.3.

After studying the proof of the Lovasz Partition Theorem in [25], MF decided that she just needed to prove a ‘little lemma’ showing that if G is any graph with detour order τ and (a, b) any pair of integers such that a + b = τ, then the vertices of G may be partitioned into two sets A and B such that τ(G[A]) ≤ a and τ(G[B]) ≤ b. The desired upper bound for $\chi _k^{\tau }$ would then follow easily. But after many fruitless attempts she realized that proving the ‘little lemma’ was not going to be so easy.

In 1995, during a visit to Peter Mihók in Slovakia, she learned that this elusive ‘little lemma’ was in fact an existing conjecture (later dubbed the Path Partition Conjecture). In 1981 Mihók and Lovász had a conversation related to the conjecture and later each of them directed a graduate student thesis on the topic. Mihók’s interest in the PPC arose from his work on a stronger conjecture, called the Path Kernel Conjecture, which we shall discuss in the next section. Lovász was attracted to the PPC since he had proved its Δ-analogue in [25]. (As explained in [20], the similarity between the PKC and the partition result of Lovász becomes clear when stated in the terminology of [3]). The PPC first appeared in 1983, in a paper by Laborde et al. [23]. The main topic of their paper was the conjecture that every digraph has an independent set meeting all longest paths (which happens to be the case a = 1 of the directed version of the PPC). However, for some reason they concluded the paper by stating the PPC for undirected graphs. Thus four different routes, explored in different parts of the globe, had led to the PPC.

Before Google, information travelled slowly, so the place to learn about existing results was at conferences or seminar coffee breaks. In November 1995, while MF was visiting Lowell Beineke, he suggested she give a talk on the PPC at a Graph Theory Day in Kalamazoo. Shortly afterwards she visited JD, who arranged for MF to give a similar talk at Clemson. We gradually learned that information on the conjecture was scarce, so in 1996 we began working on the PPC in earnest.

3 Dead Ends and Revised Routes

Throughout this paper a and b will denote positive integers. If A and B are sets of vertices in a graph G such that V (G) = A ∪ B and τ(G[A]) ≤ a and τ(G[B]) ≤ b, then we call (A, B) an (a, b)-partition of G. Our preferred formulation of the PPC is the following.

Conjecture 1 (PPC)

If G is a graph with detour order τ and (a, b) is any pair of positive integers such that a + b = τ, then G has an (a, b)-partition.

A graph that has an (a, b)-partition for every pair (a, b) such that a + b = τ(G) is called τ-partitionable.

A subset K of the vertices of a graph G is called a P _k -kernel of G if K is P _k-free and every vertex in G − K is adjacent to an end-vertex of a path of order k − 1 in K. This concept is due to our friend Peter Mihok [28], who sadly passed away on 27 March 2012.

The connection between path kernels and path partitions is given by the following proposition.

Proposition 3.1

If a graph G has a P _a+1 -kernel K and a + b = τ(G), then (K, V (G) − K) is an (a, b)-partition of G.

Proof

Let Q be a longest path in G − K and let x be an end-vertex of Q. Then x is adjacent to the end-vertex of a path P of order a in K. Since the concatenation of P and Q is a path in G, it follows that n(Q) ≤ τ(G) − a = b.

Every maximal independent set of a graph G is obviously a P ₂-kernel of G, and conversely, every P ₂-kernel is a maximal independent set. Also for every k > τ(G), the vertex set V (G) is the only P _k-kernel of G.

Vronka [30] proved that every graph has a P _k-kernel for every k ≤ 6. During a conference in Palermo we designed an algorithm for constructing a P ₇-kernel in any graph [13]. Melnikov and Petrenko showed in [26] that every graph has a P ₈-kernel, and in [27] that every graph has a P ₉-kernel. These results are summed up in the following theorem.

Theorem 3.2 ([13, 26, 27, 30])

Every graph has a P _k -kernel for every positive integer a ≤ 9.

Thus the case a ≤ 8 of the PPC is proved. We also conclude that $\chi _k^{\tau } (G)\leq n/k$ for every graph G and every positive integer k ≤ 8.

Broere, Hajnal and Mihók [6] conjectured that every graph has a P _k-kernel for every integer k ≥ 2. This conjecture, which originated from a problem stated by Mihók [28], became known as the Path Kernel Conjecture (PKC). If the PKC were true, it would obviously imply that the PPC is true.

Proving the PPC via the PKC seemed a good idea, but during a conference in Poland in 2002, we learned that Aldred and Thomassen had disproved the PKC. Their counterexample, which appears in [1], has detour order 364 and it has no P ₃₆₄-kernel. (But it obviously has a (363, 1)-partition, so the PPC still survives.) Later, Katrenic~ and Semanis~in [21] constructed a smaller counterexample to the PKC (a graph with no P ₁₅₅-kernel) and they also showed that for each integer r ≥ 0, there exists a graph with detour order τ having no P _τ−r-kernel. However, they pointed out that in each of their examples τ − r is still bigger than τ∕2. Note that if a + b = τ and a ≤ b, then a ≤ τ∕2, so in order to prove the PPC it will suffice to prove the following conjecture, for which no counterexample is as yet known.

Conjecture 2 (Revised Path Kernel Conjecture)

If G is any graph with detour order τ, then G has a P _a+1-kernel for every positive integer a ≤ τ∕2.

It could therefore still be possible to make progress towards proving the PPC by following the path kernel route. The following result of He and Wang [19] implies that the PPC holds for graphs with sufficiently large girth compared to their detour order.

Theorem 3.3 ([19])

If G is any graph with girth g, then G has a P _a+1 -kernel for every $a<\frac {3g}{2}-1$.

Corollary 3.4

If G is a graph with $g(G)> \frac {\tau (G)+2}{3}$ , then G is τ-partitionable.

A set M of vertices in a graph G is a maximal P _k+1 -free set in G if τ(G[M]) ≤ k and τ(G[M ∪{v}]) ≥ k + 1 for every vertex v in G − M. A P _k+1-kernel of G is obviously a maximal P _k+1-free set in G, but for 1 < k < τ(G) the converse is not true, as is clear from the following proposition.

Proposition 3.5 ([10])

If M is a maximal P _k+1 -free set in a graph G, 1 < k < τ(G), then for every vertex x in G − M at least one of the following holds.

• M1. There is a path P of order k in M such that x is adjacent to an end-vertex of P.

• M2. There are two vertex disjoint paths P and Q in M, each having an end-vertex adjacent to x such that n(P) + n(Q) = k.

Now let M be a maximal P _k+1-free set in a graph G, 1 ≤ k ≤ τ(G) − 1, and suppose τ(G − M) > τ(G) − k. If L is a detour of G − M, then both end-vertices of L (call them x and y) satisfy M2 of Proposition 3.5. Thus there are two vertex disjoint paths P, Q, each with an end-vertex adjacent to x, and two vertex disjoint paths R, S, each with an end-vertex adjacent to y, such that n(P) + n(Q) = n(R) + n(S) = k. Among the four paths P, Q, R, S, let P be one of maximum length. Then each of R and S is at least as long as Q, so they each intersect P and we have the situation shown in Figure 1. (Thick lines represent paths and thin lines represent edges.)

Fig. 1

A step in the proof of Theorem 3.6

These observations form the basis of the proof of the following result, which was proved in collaboration with Frank Bullock while JD was visiting MF in Pretoria in 2002.

Theorem 3.6 ([10])

If 1 ≤ k ≤ τ(G) − 1 and M is any maximal P _k+1 -free set in G, then $\tau (G-M)\leq \tau (G)- \frac {2}{3}(k+1)$ . Moreover, if k ≤ 5, then τ(G − M) ≤ τ(G) − k.

A corollary of Theorem 3.6 is that $\chi _k^{\tau }G)\leq \frac {3}{2}(\tau (G)/k)$ for every k ≥ 1. In [8] and [9] this bound is slightly improved.

In [10] we conjectured (very naively) that if 1 ≤ k ≤ τ(G) and M is any maximum P _k+1-free set in G, then τ(G − M) ≤ τ(G) − k. Aldred and Thomassen [1] easily disproved our conjecture by pointing out that if G is any hypotraceable graph with detour order τ, then G contains a maximum P _τ-free set M such that τ(G − M) = 2. (Just choose any edge xy in G and let M = V (G) −{x, y}.) However, they kindly remarked that, in order to prove the PPC, it would suffice to prove the following conjecture, for which they do not have a counterexample.

Conjecture 3

If M is any maximum P _a+1-free set in G with 1 ≤ a ≤ τ(G)∕2, then τ(G − M) ≤ τ(G) − a.

In connection with the previous two conjectures, we note that neither implies the other, but each implies the PPC.

4 The Cycle Route

Any graph without odd cycles is obviously τ-partitionable (since such a graph is bipartite and hence has a (1, 1)-partition). The proof of our first result along the cycle route uses the concept of distance sets, and is an adaptation of the classic technique for showing that graphs without odd cycles are bipartite.

Proposition 4.1 ([7])

Suppose G is a connected graph, τ(G) = a + b, a ≤ b and G contains a b-cycle. Then G has an (a, b)-partition.

Proof

Let C be a b-cycle in G and let W ₀ = V (C). For i ≥ 1, let W _i be the ith distance set with respect to C, i.e., v ∈ V (W _i) if and only if a shortest path between v and a vertex in C has length i. If L is a path in W _i, i ≥ 1, then there is a path in G that contains L as well as all the vertices on C. Hence τ(G[W _i]) ≤ a for all i ≥ 1. Now let

$$\displaystyle \begin{aligned}B=\bigcup_{i\mbox{ even}}W_i \mbox{ and } A=V(G)-B.\end{aligned}$$

Then (A, B) is an (a, b)-partition of G.

At first we thought that Proposition 4.1 leads nowhere, since the requirement that G has a cycle of length exactly b is very specific, but we included the proposition in our first PPC paper [7] for “just in case”.

The girth g(G) and circumference c(G) of a graph G are, respectively, the length of a shortest and longest cycle in G. While we were working on the sketch in Figure 1 to prove Theorem 3.6, the following result suggested itself.

Proposition 4.2 ([2])

If τ(G) = a + b and a ≤ g(G) − 1 or b ≥ c(G) − 2, then G has an (a, b)-partition.

Proof

Let A be a maximal P _a+1-free set in G. Suppose L is a path of order b + 1 in G − A. Then we have the situation depicted in Figure 1, with A = M. Note that L lies on a cycle in G that contains at least two vertices on P, so c(G) ≥ b + 3. And if C is the small cycle shown in Figure 1 that contains y and vertices of both R and S, then G contains a path of order |V (C)| + b, which implies that a ≥|V (C)|≥ g(G). $\square$

A graph is called weakly pancyclic if it has a cycle of every length between its girth and circumference. In 1998, Brandt, Faudree and Goddard [4] put weakly pancyclic graphs firmly on the map, and we noted that Propositions 4.1 and 4.2 seemed tailor-made to prove the following.

Theorem 4.3 ([10])

Every connected weakly pancyclic graph is τ-partitionable.

Proof

Suppose G is a connected weakly pancyclic graph with τ(G) = a + b, a ≤ b. If g(G) ≤ b ≤ c(G) then, since G is weakly pancyclic, G has a b-cycle, and hence G has an (a, b)-partition by Proposition 4.1. If b < g(G) or b > c(G), then it follows from Proposition 4.2 that G has an (a, b)-partition. $\square$

The proof of Theorem 4.3 now seems incredibly easy, but over the years we have had several queries as to whether we have tried proving the PPC for chordal graphs, so we rather enjoyed saying: “We have proved that the PPC holds for weakly pancyclic graphs, and chordal graphs are weakly pancyclic”.

Other interesting examples of weakly pancyclic graphs are maximal planar graphs, squares of graphs [15] and the lexicographic product of any connected graph with a graph that has at least one edge [22]. Theorem 4.3 proves the PPC for all these classes.

In [14] we call a graph G semi-pancyclic if it has a cycle of every length from ⌈τ∕2⌉ up to c(G). Our next result follows immediately from Proposition 4.2 and the fact that if a + b = τ and a ≤ b, then b ≥ τ∕2.

Theorem 4.4

Every connected semi-pancyclic graph is τ-partitionable.

It follows from Theorem 3.3 that the upper bound for a in Proposition 4.2 may be relaxed to $a<\frac {3g(G)}{2}-1$. Let us call a graph G faintly pancyclic if it has a cycle of every length from $\max \{\lfloor \frac {3g(G)}{2} - 1\rfloor , \lceil \frac {\tau (G)}{2}\rceil \}$ up to c(G) − 3. Theorem 4.4 can be expanded as follows.

Theorem 4.5

Every connnected faintly pancyclic graph is τ-partitionable.

For a given cycle C, we say that a vertex v on C is an attachment vertex if its open neighborhood contains a vertex not on C. In [14] we proved an expansion of Proposition 4.1.

Theorem 4.6

If G is a connected graph with τ(G) = a + b and G has a cycle C of length at least b with at most b attachment vertices, then G has an (a, b)-partition.

Proof

Let X be the set of attachment vertices of C and let W ₀ consist of the vertices in X together with b −|X| other vertices of C. The remainder of the proof is now the same as that of Proposition 4.1. $\square$

Corollary 4.7

Suppose a connected graph G has a circumference cycle with at most ⌈τ∕2⌉ attachment vertices. Then G is τ-partitionable.

We got into the habit of asking ourselves, whenever we encountered a nice result or a new concept: “What can it do for the PPC?” At the turn of the century, Ryjáček’s closure operation for claw-free graphs was a much discussed topic at the Cycles and Colourings workshops in Slovakia. So we naturally decided to prove the PPC for claw-free graphs. It turned out that Theorem 4.4, Corollary 4.7 and Ryjáček’s closure operation were the exact ingredients that were needed.

A graph is called claw-free if it does not contain the complete bipartite graph K _1,3 as induced subgraph. Ryjáček [29] defined the closure of a claw-free graph G in the following way. A vertex x in a claw-free graph G is eligible if the subgraph induced by the open neighbourhood N(x) of x is a connected noncomplete graph. The local completion of an eligible vertex x is the operation of joining every pair of nonadjacent vertices in G[N(x)] by an edge. The closure cl(G) of G is the graph obtained from G by recursively performing the local completion operation to eligible vertices of G until no eligible vertex remains.

A claw-free graph G is said to be closed if cl(G) = G. Brandt, Favaron and Ryjáček [5] proved the following.

Theorem 4.8 ([5])

If G is a claw-free graph, then the following hold.

• 1 cl(G) is well defined. (It is independent of the order of the eligible vertices used during the construction.)

• 2 cl(G) is also claw-free.

• 3 For every vertex v in cl(G) the graph induced by its neighbours in cl(G) is either a complete graph or the disjoint union of two complete graphs.

• 4 τ(cl(G)) = τ(G).

It follows from Theorem 4.8 that every claw-free graph is a spanning subgraph of a closed claw-free graph with the same detour order. Furthermore, every component of a claw-free graph is claw-free, and a graph has an (a, b)-partition if each of its components has an (a, b)-partition. Thus, in order to prove that the PPC holds for claw-free graphs, it is sufficient to prove that every connected, closed claw-free graph is τ-partitionable.

Observe that if C is a longest cycle in a graph G and x has a neighbour y in G − V (C), then by the maximality of C, neither the predecessor x ⁻ nor the successor x ⁺ of x is adjacent to y. Hence, if G is claw-free, it contains the short chord x ⁻ x ⁺ of C. Thus, in a claw-free graph any circumference cycle has at least as many short chords as attachment vertices. Using this fact together with Theorem 4.8, it was straightforward to obtain the following result.

Lemma 4.9 ([14])

Suppose G is a connected, closed claw-free graph such that every circumference cycle of G has more than ⌈τ(G)∕2⌉ attachment vertices. Then G is semi-pancyclic.

From Theorem 4.4, Corollary 4.7 and Lemma 4.9, we obtain the desired result.

Theorem 4.10 ([14])

Every claw-free graph is τ-partitionable.

A cograph, or complement-reducible graph, is a graph that can be generated from the single-vertex graph K ₁ by complementation and disjoint union. Thus the class of cographs is the smallest class of graphs that includes K ₁ and is closed under complementation and disjoint union. Corneil, Lerchs and Burlingham [12] established several interesting characterizations of cographs, among them the following:

Theorem 4.11

A graph G is a cograph if and only if G does not contain the path P ₄ as induced subgraph.

During a recent workshop at Salt Rock on the Kwazulu-Natal coast, the participants (Ortrud Oellermann, Johan de Wet, JD and MF) observed that it follows from the above characterization and Corollary 4.7 that the PPC holds for cographs. We present the proof here.

Theorem 4.12

Every cograph is τ-partitionable.

Proof

Let C be a circumference cycle of a connected cograph G. Suppose C has more than τ(G)∕2 attachment vertices. Then there are two consecutive vertices u, v on C with respective neighbours x, y in G − V (C). But then xuvy is an induced P ₄ by the maximality of C, contradicting Theorem 4.11. This proves that C has at most τ(G)∕2 attachment vertices, and hence G is τ-partitionable by Corollary 4.7. We conclude that every component of a cograph is τ-partitionable, and this implies that every cograph is τ-partitionable. $\square$

A block of a graph G is a maximal 2-connected subgraph of G. Another important consequence of Proposition 4.2 is this one.

Theorem 4.13 ([13])

If every 2-connected graph is τ-partitionable, then every graph is τ-partitionable.

Proof

The proof is by induction on the number of blocks. Suppose G is a graph with more than one block and τ(G) = a + b. By Proposition 4.2 we may assume that b < c(G), so G has a block X that contains a cycle C with at least b vertices. Let Z be an end-block of G, with Z ≠ X and denote its cut-vertex by z. Let G′ = G − (V (Z) − z). By our induction hypothesis, G′ has an (a, b)-partition. Let D _i = {v ∈ Z : d(v, z) = i}. Then, since there is a path from z to the cycle C in G′, the detour order of each distance set D _i is less than a, so by the technique used in the proof of Proposition 4.1, we obtain an (a, a)-partition of Z. Combining it with the (a, b)-partition of G′, we obtain an (a, b)-partition of G. $\square$

We call a graph G detour-saturated if τ(G + xy) > τ(G) for every pair of nonadjacent vertices x, y in G. A detour-saturated graph with detour order k is called k-detour-saturated. If G is a graph with detour order k, then G is obviously contained in a k-detour-saturated graph G ^∗, and if G ^∗ is τ-partitionable, then so is G. Thus, in view of Theorems 4.5, 4.7 and 4.13, proving the following conjecture will prove the PPC.

Conjecture 4

If G is any 2-connected non-bipartite detour-saturated graph such that every circumference cycle of G has at least τ(G)∕2 attachment vertices, then G is faintly pancyclic.

We began investigating detour-saturated graphs in collaboration with Lowell Beineke at a Salt Rock workshop in 2001. In the paper [2] that resulted from this workshop, we conjectured that every bipartite detour-saturated graph is acyclic. If this is the case, the “non-bipartite” condition may be omitted from Conjecture 4.

5 Are We There Yet?

The detour deficiency p(G) of a graph G is the difference between its order and its detour order. A graph with detour deficiency p is called p-deficient. A 0-deficient graph is also called a traceable graph.

Now suppose G is a p-deficient graph and a + b = τ(G), a ≤ b. Then the order of G is a + b + p. If p = 0, then an (a, b)-partition of G can obviously be obtained by placing any a vertices in A and the remaining b vertices in B. If G is 1-deficient, it follows from Dirac’s classic degree condition for traceability that G has a vertex x of degree at most $\frac {\tau (G)}{2}\leq b$. Thus we can choose a set B of exactly b vertices from G − x such that N(x) ⊆ B. Now, if A = V (G) − B, then |A| = a + 1 and τ(G[A]) ≤ a, since x has no neighbour in A. Thus (A, B) is an (a, b)-partition of G.

During the final coffee break at the International Conference in Graph Theory in the Ithala Game Reserve in 2001, Ingo Schiermeyer suggested that we try to extend the above partition strategy for graphs with larger deficiency. In general, if a ≤ b the strategy would be to find a set X consisting of p vertices such that X has at most τ(G)∕2 neighbours in G − X. Ingo eventually succeeded in carrying out the strategy for p = 2, 3, so the following result is proved.

Theorem 5.1 ([16])

For 0 ≤ p ≤ 3, every p-deficient graph is τ-partitionable.

For p-deficient graphs with p > 3, Ingo managed to get his partition strategy to work for graphs of sufficiently large order in relation to p. He achieved this by considering attachment vertices and independent sets on longest paths and applying our cycle route strategy (in particular, Theorem 4.2 and Corollary 4.7). This culminated in the following asymptotic result for the PPC. (Ingo proved the crucial step in 2003, during a two-hour journey from the Pilanesberg Game Reserve to Pretoria.)

Theorem 5.2 ([16])

For p ≥ 4, every p-deficient graph of order at least 10p ² − 3p is τ-partitionable.

Theorem 5.2 seems to indicate that the end of our journey is almost in sight. But the horizon is forever shifting.

6 Uncharted Routes

In this section we discuss a few open problems that have crossed our path during our PPC journey. The ideas and techniques presented in the previous sections go some way towards solving them, but not far enough. Perhaps the reader can contribute some innovative new ideas for making further progress or even solving these problems.

• 1. Does the PPC hold for planar graphs?. We know that every maximal planar graph is weakly pancyclic and hence τ-partitionable, but that does not necessarily imply that all planar graphs are τ-partitionable. (Note that if edges are added to a planar graph to obtain a maximal planar graph, the detour order may increase.) The only results that we have found on this problem are the following, by Glebov and Zambalaeva [18].

  Theorem 6.1 ([18]) The PPC holds for planar graphs with girths 5, 8, 9 and 16. Moreover, planar graphs with girths 8, 9 and 16 have a (2, 3)-partition, a (2, 2)-partition and a (1, 2)-partition, respectively.

• 2. Does the PPC hold for locally connected graphs? A graph G is locally connected if for each v ∈ V (G), the graph induced by the open neighbourhood N(v) of v is connected. Ryjáček [31] conjectured that every locally connected graph is weakly pancyclic. If his conjecture is true, it would imply that every locally connected graph is τ-partitionable. Ryjacek’s Conjecture seems a tough nut to crack, so we suggest trying to prove the following weaker conjecture, which would still imply that every locally connected graph is τ-partitionable.

  Conjecture 5 If G is any connected locally connected graph such that every circumference cycle of G has at least τ(G)∕2 attachment vertices, then G is faintly pancyclic.

• 3. One could consider replacing ‘locally connected’ in Problem 2 with ‘locally traceable’ or ‘locally hamiltonian’.