Colourings of (k-r,k)-trees
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 \(...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
AGH Univeristy of Science and Technology Press
2017-01-01
|
| Series: | Opuscula Mathematica |
| Subjects: | |
| Online Access: | http://www.opuscula.agh.edu.pl/vol37/4/art/opuscula_math_3724.pdf |
| _version_ | 1811300525980778496 |
|---|---|
| author | M. Borowiecki H. P. Patil |
| author_facet | M. Borowiecki H. P. Patil |
| author_sort | M. Borowiecki |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-13T06:53:32Z |
| format | Article |
| id | doaj.art-d90ca3a63f694327be52095a51c91c38 |
| institution | Directory Open Access Journal |
| issn | 1232-9274 |
| language | English |
| last_indexed | 2024-04-13T06:53:32Z |
| publishDate | 2017-01-01 |
| publisher | AGH Univeristy of Science and Technology Press |
| record_format | Article |
| series | Opuscula Mathematica |
| spelling | doaj.art-d90ca3a63f694327be52095a51c91c382022-12-22T02:57:20ZengAGH Univeristy of Science and Technology PressOpuscula Mathematica1232-92742017-01-01374491500http://dx.doi.org/10.7494/OpMath.2017.37.4.4913724Colourings of (k-r,k)-treesM. Borowiecki0H. P. Patil1University of Zielona Góra, Faculty of Mathematics, Computer Science and Econometrics, ul. Prof. Z. Szafrana 4a, 65-516 Zielona Góra, PolandPondicherry University, Department of Mathematics, Puducherry - 605 014, IndiaTrees 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.http://www.opuscula.agh.edu.pl/vol37/4/art/opuscula_math_3724.pdfchromatic polynomialpartition numbercolouringtree |
| spellingShingle | M. Borowiecki H. P. Patil Colourings of (k-r,k)-trees Opuscula Mathematica chromatic polynomial partition number colouring tree |
| title | Colourings of (k-r,k)-trees |
| title_full | Colourings of (k-r,k)-trees |
| title_fullStr | Colourings of (k-r,k)-trees |
| title_full_unstemmed | Colourings of (k-r,k)-trees |
| title_short | Colourings of (k-r,k)-trees |
| title_sort | colourings of k r k trees |
| topic | chromatic polynomial partition number colouring tree |
| url | http://www.opuscula.agh.edu.pl/vol37/4/art/opuscula_math_3724.pdf |
| work_keys_str_mv | AT mborowiecki colouringsofkrktrees AT hppatil colouringsofkrktrees |