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

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