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
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.
- 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.
- J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, 2008.
- 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.
- M. Borowiecki, I. Broere, Hamiltonicity and generalized total colourings of planar graphs, Discuss. Math. Graph Theory 36 (2016), 243-257.
- M. Borowiecki, W. Chojnacki, Chromatic index of \(k\)-trees, Discuss. Math. 9 (1988), 55-58.
- C.Y. Cho, N.Z. Li, S.J. Xu, On \(q\)-trees, J. Graph Theory 10 (1986), 129-136.
- A.K. Dewdney, Higher-dimensional tree structures, J. Combin. Theory Ser. B 17 (1974), 160-169.
- I.G. Dmitriev, Characterization of \(k\)-trees, Sb. trudov Inst. Mat. Sibirsk. Otd. Akad. Nauk USSR 38 (1982), 9-18 [in Russian].
- M. Gionfriddo, Characterizations and properties of the \((m,n)\)-trees, J. Comb. Inf. System Sci. 7 (1982), 297–302.
- F. Harary, Graph Theory, Addison-Wesley, Reading Mass., 1969.
- F. Harary, E.M. Palmer, On acyclic simplicial complexes, Mathematika 15 (1968), 115-122.
- D.R. Lick, A.T. White, \(k\)-degenerate graphs, Canad. J. Math. 22 (1970), 1082-1096.
- H.P. Patil, Studies on \(k\)-trees and some related topics, PhD Thesis, University of Warsaw, Poland, 1984.
- M. Plantholt, The chromatic index of graphs with a spanning star, J. Graph Theory 5 (1981), 5-13.
- 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.
- V.G. Vizing, On the estimate of the chromatic class of a \(p\)-graph, Diskret. Analiz 3 (1964), 25-30 [in Russian].
- 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.
- Received: 2016-08-23.
- Revised: 2017-01-26.
- Accepted: 2017-01-27.
- Published online: 2017-04-28.
