Colourings of (k-r,k)-trees

Abstract

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\neq 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.