- Tytuł:
- Acyclic sum-list-colouring of grids and other classes of graphs
- Autorzy:
-
Drgas-Burchardt, E.
Drzystek, A. - Powiązania:
- https://bibliotekanauki.pl/articles/254959.pdf
- Data publikacji:
- 2017
- Wydawca:
- Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
- Tematy:
-
sum-list colouring
acyclic colouring
grids
generalized Petersen graphs - Opis:
- 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.
- Źródło:
-
Opuscula Mathematica; 2017, 37, 4; 535-556
1232-9274
2300-6919 - Pojawia się w:
- Opuscula Mathematica
- Dostawca treści:
- Biblioteka Nauki
Artykuł