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

Opuscula Mathematica

# Colourings of (k-r,k)-trees

M. Borowiecki
H. P. Patil

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.

Full text (pdf)

1. L.W. Beineke, R.E. Pippert, On the structure of $$(m,n)$$-trees, [in:] Proc. 8th S-E Conf. Combinatorics, Graph Theory and Computing, 1977, pp. 75-80.
2. J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, 2008.
3. M. Borowiecki, Two extremal problems in the class of uniquely colourable graphs, [in:] M. Borowiecki, Z. Skupień (eds.), Graphs, Hypergraphs and Matroids II, Zielona Góra, 1987, pp. 17-25.
4. M. Borowiecki, I. Broere, Hamiltonicity and generalized total colourings of planar graphs, Discuss. Math. Graph Theory 36 (2016), 243-257.
5. M. Borowiecki, W. Chojnacki, Chromatic index of $$k$$-trees, Discuss. Math. 9 (1988), 55-58.
6. C.Y. Cho, N.Z. Li, S.J. Xu, On $$q$$-trees, J. Graph Theory 10 (1986), 129-136.
7. A.K. Dewdney, Higher-dimensional tree structures, J. Combin. Theory Ser. B 17 (1974), 160-169.
8. I.G. Dmitriev, Characterization of $$k$$-trees, Sb. trudov Inst. Mat. Sibirsk. Otd. Akad. Nauk USSR 38 (1982), 9-18 [in Russian].
9. M. Gionfriddo, Characterizations and properties of the $$(m,n)$$-trees, J. Comb. Inf. System Sci. 7 (1982), 297–302.
11. F. Harary, E.M. Palmer, On acyclic simplicial complexes, Mathematika 15 (1968), 115-122.
12. D.R. Lick, A.T. White, $$k$$-degenerate graphs, Canad. J. Math. 22 (1970), 1082-1096.
13. H.P. Patil, Studies on $$k$$-trees and some related topics, PhD Thesis, University of Warsaw, Poland, 1984.
14. M. Plantholt, The chromatic index of graphs with a spanning star, J. Graph Theory 5 (1981), 5-13.
15. Z. Skupień, Stirling numbers and colouring of $$q$$-trees, Prace Naukowe Inst. Mat. Polit. Wrocław., no. 17, Ser. Studia i Materiały, no. 13, Grafy, Hipergrafy, Systemy Bloków (1977), 63-67.
16. V.G. Vizing, On the estimate of the chromatic class of a $$p$$-graph, Diskret. Analiz 3 (1964), 25-30 [in Russian].
17. V.G. Vizing, Critical graphs with a given chromatic class, Diskret. Analiz 5 (1965), 9-17 [in Russian].
• M. Borowiecki
• University of Zielona Góra, Faculty of Mathematics, Computer Science and Econometrics, ul. Prof. Z. Szafrana 4a, 65-516 Zielona Góra, Poland
• H. P. Patil
• Pondicherry University, Department of Mathematics, Puducherry - 605 014, India
• Communicated by Dalibor Fronček.
• Revised: 2017-01-26.
• Accepted: 2017-01-27.
• Published online: 2017-04-28.