(𝒌,𝒄)-Choosability of cycle graphs, wheel graphs and generalized Petersen graphs 𝐆𝐏(𝒏,𝟏)
| dc.contributor.author | Sajeena, K. D. | |
| dc.contributor.author | Almeida, S. V. A. | |
| dc.contributor.author | Wijesiri, G. S. | |
| dc.contributor.author | Dencil, J. A. D. M. | |
| dc.date.accessioned | 2024-10-29T08:01:37Z | |
| dc.date.available | 2024-10-29T08:01:37Z | |
| dc.date.issued | 2024-11-01 | |
| dc.description.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 | |
| dc.identifier.citation | Proceedings of the Postgraduate Institute of Science Research Congress (RESCON) -2024, University of Peradeniya, P 59 | |
| dc.identifier.issn | 3051-4622 | |
| dc.identifier.uri | https://ir.lib.pdn.ac.lk/handle/20.500.14444/2784 | |
| dc.language.iso | en | |
| dc.publisher | Postgraduate Institute of Science (PGIS), University of Peradeniya, Sri Lanka | |
| dc.relation.ispartofseries | Volume 11 | |
| dc.subject | 𝑘-choosable | |
| dc.subject | List colouring | |
| dc.subject | Planar graphs | |
| dc.title | (𝒌,𝒄)-Choosability of cycle graphs, wheel graphs and generalized Petersen graphs 𝐆𝐏(𝒏,𝟏) | |
| dc.type | Article |