Name
Abstract | ||
|---|---|---|
For a graph G, the path number tau(G) is defined as the order of a longest path in G. An (m, k)(tau)-colouring of a graph H is a partition of the vertex set of H into in subsets such that each subset induces a subgraph of H for which tau is at most k. The k-tau-chromatic number chi(k)(tau)(H) is the least in for which H has an (m, k)(tau)-colouring. A graph H is uniquely (m, k)(tau)-colourable if chi(k)(tau)(H)=m and there is only one partition of the vertex set of H which is an (m, k)(tau)-colouring of H. A graph G is called k-tau-saturated if tau(G)less than or equal to k and tau(G+e)greater than or equal to k+1 for all e is an element of(<E(G)over bar>). For k=1, the graphs obtained by taking the join of k-tau-saturated graphs (which are empty graphs in this case) are known to be uniquely colourable graphs. In this paper we construct uniquely (m, k)(tau)-colourable graphs (for all positive integers m and k) using k-tau-saturated graphs in a similar fashion. As a corollary we characterise those p for which there exists a uniquely (m, k)(tau)-colourable graph of order p. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1016/0012-365X(95)00301-C | Discrete Mathematics |
Keywords | DocType | Volume |
colourable graph,longest path | Journal | 162 |
Issue | ISSN | Citations |
1-3 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gerhard Benadé | 1 | 0 | 0.34 |
| Izak Broere | 2 | 143 | 31.30 |
| Betsie Jonck | 3 | 0 | 0.34 |
| Marietjie Frick | 4 | 191 | 33.21 |