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

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.

Referred to by Corrigendum to <a href="https://repo.agh.edu.pl/handle/AGH/112848">Referred to by Corrigendum to Acyclic sum-list-colouring of grids and other classes of graphs Article: Opuscula Math. 38, no. 6 (2018), 899-901</a>, https://doi.org/10.7494/OpMath.2018.38.6.899