Powiadomienia systemowe
- Sesja wygasła!
- Sesja wygasła!
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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 ≠ 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.
Słowa kluczowe
Czasopismo
Rocznik
Tom
Strony
491--500
Opis fizyczny
Bibliogr. 17 poz.
Twórcy
autor
- University of Zielona Góra Faculty of Mathematics, Computer Science and Econometrics ul. Prof. Z. Szafrana 4a, 65-516 Zielona Góra, Poland
autor
- Pondicherry University Department of Mathematics Puducherry - 605 014, India
Bibliografia
- [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, Hamiltonidty 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].
Uwagi
PL
Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-7c5a85d4-0180-431c-be54-87d49945d40b