Colourings of (k - r, k)-trees

Trees are generalized to a special kind of higher dimensional complexes known as (j, k)-trees ([L.W. Beineke, R.E. Pippert, On the structure of (m,n)-trees, Proc. 8th S-E Conf. Combinatorics, Graph Theory and Computing, 1977, 75-80]), and which are a natural extension of k-trees for j = k—1. The aim of this paper is to study (k — r, k)-trees ([H.P. Patil, Studies on k-trees and some related topics, PhD Thesis, University of Warsaw, Poland, 1984]), which are a generalization of k-trees (or usual trees when k = 1). We obtain the chromatic polynomial of (k — r, k)-trees and show that any two (k — r, k)-trees of the same order are chromatically equivalent. However, if r ≠ 1 in any (k — r, k)-tree G, then it is shown that there exists another chromatically equivalent graph H, which is not a (k — r, k)-tree. Further, the vertex-partition number and generalized total colourings of (k — r, k)-trees are obtained. We formulate a conjecture about the chromatic index of (k — r, k)-trees, and verify this conjecture in a number of cases. Finally, we obtain a result of [M. Borowiecki, W. Chojnacki, Chromatic index of k-trees, Discuss. Math. 9 (1988), 55-58] as a corollary in which k-trees of Class 2 are characterized.