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

✍ Scribed by Gerhard Benadé; Izak Broere; Betsie Jonck; Marietjie Frick

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 518 KB
• Volume: 162
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00301-c

✦ Synopsis

For a graph G, the path number r(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 r is at most k. The k -z-chromatic number z~(H) is the least m for which H has an (m, kf-colouring. A graph H is uniquely (m, kf-colourable if z~(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 -r-saturated if r(G) ~ k and z(G + e) ~> k + 1 for all e e E(G). For k = 1, the graphs obtained by taking the join of k -z-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 -r-saturated graphs in a similar fashion. As a corollary we characterise those p for which there exists a uniquely (m, kfcolourable graph of order p.