Opuscula Math. 37, no. 4 (2017), 535-556
http://dx.doi.org/10.7494/OpMath.2017.37.4.535

Opuscula Mathematica

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

Ewa Drgas-Burchardt
Agata Drzystek

Abstract. 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 $$D_1$$-sum-choice-number of $$G$$. In the paper we investigate the $$D_1$$-sum-choice-number of graphs with small degrees. Especially, we give the exact value of the $$D_1$$-sum-choice-number for each grid $$P_n\square P_m$$, when at least one of the numbers $$n$$, $$m$$ is less than five, and for each generalized Petersen graph. Moreover, we present some results that estimate the $$D_1$$-sum-choice-number of an arbitrary graph in terms of the decycling number, other graph invariants and special subgraphs.

Keywords: sum-list colouring, acyclic colouring, grids, generalized Petersen graphs.

Mathematics Subject Classification: 05C30, 05C15.

Full text (pdf)

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. Erdös, 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 $$2 \times n$$ 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.
• Ewa Drgas-Burchardt
• University of Zielona Góra, Faculty of Mathematics, Computer Science and Econometrics, ul. Prof. Z. Szafrana 4a, 65-516 Zielona Góra, Poland
• Agata Drzystek
• University of Zielona Góra, Faculty of Mathematics, Computer Science and Econometrics, ul. Prof. Z. Szafrana 4a, 65-516 Zielona Góra, Poland
• Communicated by Ingo Schiermeyer.
• Revised: 2016-12-23.
• Accepted: 2017-01-11.
• Published online: 2017-04-28.