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.
  10. F. Harary, Graph Theory, Addison-Wesley, Reading Mass., 1969.
  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.
  • Received: 2016-08-23.
  • Revised: 2017-01-26.
  • Accepted: 2017-01-27.
  • Published online: 2017-04-28.
Opuscula Mathematica - cover

Cite this article as:
M. Borowiecki, H. P. Patil, Colourings of (k-r,k)-trees, Opuscula Math. 37, no. 4 (2017), 491-500, http://dx.doi.org/10.7494/OpMath.2017.37.4.491

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.