TY  - JOUR
ID  - Borowiecki2017
LB  - Borowiecki2017
AU  - Borowiecki, M.
AU  - Patil, H. P.
TI  - Colourings of (k-r,k)-trees
ST  - Colourings of (k-r,k)-trees
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2017
VL  - 37
IS  - 4
SP  - 491
EP  - 500
DO  - http://dx.doi.org/10.7494/OpMath.2017.37.4.491
UR  - http://dx.doi.org/10.7494/OpMath.2017.37.4.491
AB  - 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.
KW  - chromatic polynomial
KW  - partition number
KW  - colouring
KW  - tree
SN  - 1232-9274
ER  -