(𝒌,𝒄)-Choosability of cycle graphs, wheel graphs and generalized Petersen graphs 𝐆𝐏(𝒏,𝟏)

Loading...
Thumbnail Image

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

Citation

Proceedings of the Postgraduate Institute of Science Research Congress (RESCON) -2024, University of Peradeniya, P 59

Collections