(k, c) – Choosability of cycle graphs, wheel graphs, and n – prism graphs

Abstract

A graph is called L – list colourable if there exists a vertex colouring of the graph in which the colour assigned to a vertex is chosen from a list L associated with the vertex. A graph is called k – choosable if it is L – list colourable for every assignment of lists L where each L has exactly k elements. A (k, c) – list assignment L or simply a (k, c) – assignment L of a graph is a function that assigns exactly k colors to each vertex while ensuring that any two adjacent vertices share at most c common colors. A graph G is said to be (k, c) – choosable if there exists an L– list colouring of G for every (k, c) – assignment L. The (k, c) – choosability concept in graph theory is highly relevant in real-world applications involving resource allocation, scheduling, network optimization, and security. By ensuring a valid assignment of resources under constraints, it provides a powerful mathematical framework for solving practical problems in various domains. While it is a powerful generalization of graph colouring, determining whether a graph is (k, c) – choosable is computationally difficult, especially for large and complex graphs and it strongly depends on its structure. To overcome these limitations, this study explores three families of planar graphs: cycle graphs, wheel graphs, and n – prism graphs, aiming to determine the values of k and c for families of planar graphs that are (k, c) – choosable. Earlier studies on (k, c) – choosability of planar graphs were reviewed and the methods used in the findings were applied to complete this study. It was proved that the cycle graph Cn and the n – prism graph are 3 – choosable, (k,3) – choosable for any k ≥ 3 and (3, t) – choosable for t = 1, 2, 3 where as the wheel graph Wn was shown to be 4 – choosable,(k, 4) – choosable for any k ≥ 4, and (4, t) – choosable for t = 1, 2, 3, 4, establishing precise values of k and c for which cycle graphs, wheel graphs, and n – prism graphs are (k, c) – choosable, expanding upon existing results in list colouring. These findings enhance the understanding of (k, c) – choosability and may facilitate further research in graph colouring and its applications.