Acyclic sum-list-colouring of grids and other classes of graphs

• Autorzy: Drgas-Burchardt E. , Drzystek A.

Identyfikatory

DOI

10.7494/OpMath.2017.37.4.535

• Języki publikacji: EN

Abstrakty

EN

In this paper we consider list colouring of a graph G in which the sizes of lists assigned to different vertices can be different. We colour G from the lists in such a way that each colour class induces an acyclic graph. The aim is to find the smallest possible sum of all the list sizes, such that, according to the rules, G is colourable for any particular assignment of the lists of these sizes. This invariant is called the D1-sum-choice-number of G. In the paper we investigate the D1-sum-choice-number of graphs with small degrees. Especially, we give the exact value of the D1-sum-choice-number for each grid [formula], when at least one of the numbers n, rn is less than five, and for each generalized Petersen graph. Moreover, we present some results that estimate the D1-sum-choice-number of an arbitrary graph in terms of the decycling number, other graph invariants and special subgraphs.

Słowa kluczowe

EN

sum-list colouring; acyclic colouring; grids; generalized Petersen graphs

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

Twórcy

autor

Drgas-Burchardt E.

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

autor

Drzystek A.

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

Bibliografia

• [1] L.W. Beineke, R.C. Vandell, Decycling graphs, J. Graph Theory 25 (1996), 59-77.
• [2] M. Borowiecki, P. Mihók, Hereditary properties of graphs, [in:] V.R. Kulli (ed.), Advances in Graph Theory, Vishawa International Publication, Gulbarga, 1991, 41-68.
• [3] R. Diestel, Graph Theory, 2nd ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, New York, 2000.
• [4] E. Drgas-Burchardt, A. Drzystek, General and acyclic sum-list-colouring of graphs, Appl. Anal. Discrete Math. 10 (2016) 2, 479-500.
• [5] L. Gao, X. Xu, J. Wang, D.Zhu, Y. Yang, The decycling number of generalized Petersen graphs, Discrete Appl. Math. 181 (2015), 297-300.
• [6] P. Erdos, A.L. Rubin, H. Taylor, Choosability in graphs, [in:] Proceedings West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata CA, Congr. Numer. 26 (1979).
• [7] G. Isaak, Sum list coloring 2xti arrays, Electron. J. Combin. 9 (2002) #N8.
• [8] E. Kubicka, A.J. Schwenk, An introduction to chromatic sums, [in:] Proceedings of the Seventeenth Annual ACM Computer Sciences Conference, ACM Press (1989), 39-45.
• [9] M. Lastrina, List-coloring and sum-list-coloring problems on graphs, Ph.D. Thesis, Iowa State University, 2012.
• [10] F.L. Luccio, Almost exact minimum feedback vertex sets in meshes and butterflies, Inform. Process. Lett. 66 (1998), 59-64.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).