Exploring Chromatic Polynomials: Theory and Applications in Graph Colouring

Exploring Chromatic Polynomials: Theory and Applications in Graph Colouring

Ms. Adhira C

Assistant Professor of Mathematics,

Nilgiri College of Arts and Science, Thaloor, India.

Abstract: Chromatic polynomials serve as a fundamental tool in graph theory for analyzing vertex colorings and counting the number of proper color assignments in graphs. This paper explores the theoretical foundation of chromatic polynomials, including key definitions, properties, and recursive computation methods such as the deletion-contraction technique. It also highlights practical applications in scheduling, register allocation, wireless frequency assignment, and social network analysis, demonstrating the broad relevance of graph coloring concepts in conflict-free resource allocation. Finally, the discussion addresses computational challenges and connections to advanced topics, underscoring the importance of chromatic polynomials in both theoretical and applied mathematics.

Keywords: Chromatic Polynomial, Graph Coloring, Deletion-Contraction Method, Scheduling Problems, Register Allocation.