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)