Opuscula Math. 37, no. 4 (), 491-500
http://dx.doi.org/10.7494/OpMath.2017.37.4.491
Opuscula Mathematica

# 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.
Keywords: chromatic polynomial, partition number, colouring, tree.
Mathematics Subject Classification: 05C75.