On the (k,c)- choosability of tri-partite graphs

Abstract

Graph colouring is a fundamental concept in graph theory with diverse real-world applications. List colouring is a key concept in graph colouring where vertices are coloured using an available list of possible colours. Proper list colouring guarantees that no two adjacent vertices share the same colour. If every vertex is assigned a list of k possible colours and the graph admits a proper list colouring, then the graph is said to be k-choosable. A graph G = (V, E) is referred to as (k, c)- choosable (k> c) if for each list  assignment  L  satisfying IL(v)l > k for each vertex v and IL(x)∩L(y)l s <c for each edge xy .   This  research primarily   investigates  the  (k, c)- choosability of tri-partite graphs, with a specific focus on k1qr graph which has significant applications,  spanning multiple domains.  The analysis begins by viewing the complete tripartite graph k1qr as a structure composed of three distinct levels, where each level contains 1,q and r vertices, respectively, each corresponding to one of the three independent partitions of the graph, and the assignment of colours is done in each level adhering to proper colouring with a given list of colours. This study proves that the complete tripartite graph k1qr is 3- choosable by mathematical induction.