List Coloring of the Unitary Divisor Graphs
G. Thamizhendhi *
Sri Vasavi College, Erode, Tamil Nadu, India.
V. Abirami
Sri Vasavi College, Erode, Tamil Nadu, India.
*Author to whom correspondence should be addressed.
Abstract
This paper studies the list coloring properties of divisor graphs and important variants, with emphasis on unitary divisor graphs and unitary prime divisor graphs (the unitary coprime divisor graph coincides with the unitary divisor graph). In list coloring, each vertex receives a list of permissible colors and a proper coloring selects one color from each list so that adjacent vertices receive different colors. The work compares the chromatic number and list chromatic number for selected divisor-based graphs and presents explicit graph constructions and list-coloring examples. For \(\operatorname{UDG}(n)\) with \(r\) distinct prime factors, it is shown that \(\chi(\operatorname{UDG}(n))=r+1\) and \(r+1 \leq \chi_{\ell}(\operatorname{UDG}(n)) \leq 2^r\), with \(\chi_{\ell}(\operatorname{UDG}(n))=r+1\) whenever \(r \leq 4\). An illustrative encoding of a small timetabling problem is also given, where vertices represent teachers, edges represent declared conflicts, and colors represent available time periods. The study illustrates how arithmetic structure and list-coloring constraints can be combined to encode availability restrictions.
Keywords: List coloring, choosability, list chromatic number, unitary divisor graph, unitary prime divisor graph, graphs, timetable encoding