Uniquely (m, k)τ-colourable graphs and k − τ-saturated graphs Original Research Article

For a graph G, the path number τ(G) is defined as the order of a longest path in G. An (m, k)τ-colouring of a graph H is a partition of the vertex set of H into m subsets such that each subset induces a subgraph of H for which τ is at most k. The k − τ-chromatic number χkτ(H) is the least m for which H has an (m, k)τ-colouring. A graph H is uniquely (m, k)τ-colourable if χkτ(H) = m and there is only one partition of the vertex set of H which is an (m, k)τ-colouring of H. A graph G is called k − τ-saturated if τ(G) ⩽ k and τ(G + e) ⩾ k + 1 for all e ϵ E(G). For k = 1, the graphs obtained by taking the join of k − τ-saturated graphs (which are empty graphs in this case) are known to be uniquely colourable graphs. In this paper we construct uniquely (m, k)τ-colourable graphs (for all positive integers m and k) using k − τ-saturated graphs in a similar fashion. As a corollary we characterise those p for which there exists a uniquely (m, k)τ-colourable graph of order p.