Colourings of (k - r, k)-trees

• Autorzy: Borowiecki M. , Patil H. P.

Identyfikatory

DOI

10.7494/OpMath.2017.37.4.491

• Języki publikacji: EN

Abstrakty

EN

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

EN

chromatic polynomial; partition number; colouring; tree

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2017
• Tom: Vol. 37, no. 4
• Strony: 491--500
• Opis fizyczny: Bibliogr. 17 poz.

Twórcy

autor

Borowiecki M.

• University of Zielona Góra Faculty of Mathematics, Computer Science and Econometrics ul. Prof. Z. Szafrana 4a, 65-516 Zielona Góra, Poland

autor

Patil H. P.

• 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).