General and acyclic sum-list-colouring of graphs
Author(s) -
Ewa DrgasBurchardt,
Agata Drzystek
Publication year - 2016
Publication title -
applicable analysis and discrete mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.69
H-Index - 26
eISSN - 2406-100X
pISSN - 1452-8630
DOI - 10.2298/aadm161011026d
Subject(s) - mathematics , combinatorics , discrete mathematics
We investigate list colouring of a graph in which the sizes of the lists assigned to different vertices can be different. For a given graph G and a class of graphs P we colour G from the lists in such a way that each colour class induces a graph in P . The aim is to find the P-sum-choice-number of G, which means 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. We prove several general results concerning the P-sum-choice-number of an arbitrary graph. Using some of them, we also estimate or, in the case of complete graphs or some complete bipartite graphs, exactly determine the P-sum-choice-number of a graph, when P is the class of acyclic graphs.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom