Acyclic sum-list-colouring of grids and other classes of graphs
Ewa Drgas‐Burchardt, Agata Drzystek · Opuscula Mathematica · 2017
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 Pn Pm, 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 D1-sum-choice-number of an arbitrary graph in terms of the decycling number, other graph invariants and special subgraphs.