(𝒌,𝒄)-Choosability of cycle graphs, wheel graphs and generalized Petersen graphs 𝐆𝐏(𝒏,𝟏)
Date
2024-11-01
Authors
Sajeena, K. D.
Almeida, S. V. A.
Wijesiri, G. S.
Dencil, J. A. D. M.
Journal Title
Journal ISSN
Volume Title
Publisher
Postgraduate Institute of Science (PGIS), University of Peradeniya, Sri Lanka
Abstract
List colouring is a way of graph colouring used in graph theory, in which each vertex can be
assigned a list of permissible colours. A graph is deemed 𝑘-choosable, or 𝑘-list colourable
if it can be properly list coloured regardless of the specific assignment of a list containing 𝑘
colours to each vertex. The aim of this research was to understand the concept of 𝐿-list
colourability for every (𝑘, 𝑐)-assignment 𝐿 of any planar graph and identify values for 𝑘 and
𝑐 of three families of planar graphs: the cycle graphs, wheel graphs and generalized Petersen
graphs of the form GP(𝑛, 1) that are (𝑘, 𝑐)-choosable. Earlier studies on (𝑘, 𝑐)-choosability
of planar graphs were reviewed, and the methods used in the findings were applied to
complete the research problem. Significant results relating to the relationship between 𝑘-
choosability, (𝑘, 𝑐)-choosability, and the list chromatic number for any graph 𝐺 were proved
in this research. It was proved that the cycle graph 𝐶𝑛 and generalized Petersen graphs
GP(𝑛, 1) are 3-choosable for any 𝑛 ≥ 3, (𝑘, 3)-choosable for any 𝑘 ≥ 3 and (3,𝑡)-
choosable for t = 1, 2, 3. Also, the wheel graph 𝑊𝑛 is 4-choosable, (, 4)-choosable for
any 𝑘 ≥ 4 and (4, 𝑡)-choosable for 𝑡 = 1, 2, 3, 4. Specific values for 𝑘 and 𝑐 for the
existence of (𝑘, 𝑐)-choosability were found for all three families of planar graphs.
Keywords: (𝑘, 𝑐)-assignment, (𝑘, 𝑐)-choosability, 𝑘-choosable, List colouring, Planar
graphs
Description
Keywords
𝑘-choosable , List colouring , Planar graphs
Citation
Proceedings of the Postgraduate Institute of Science Research Congress (RESCON) -2024, University of Peradeniya, P 59