Article
Innovative Strategies for Node Colouring and Novel Upper Bounds on Chromatic Numbers
Graph theory is a foundational discipline in mathematics with numerous practical applications in computer science, operations research, and network design. Among its fundamental problems, vertex coloring, and the determination of chromatic numbers are central topics of study. This paper introduces innovative approaches and novel insights into these areas, offering advanced methods for solving long-standing problems.The vertex colouring problem seeks to assign colors to the vertices of a graph in such a way that no adjacent vertices share the same color. Finding the minimum number of colours required, known as the chromatic number, is a classic problem. Traditional algorithms and heuristics have limitations in finding precise chromatic numbers for complex graphs. In this work, we propose a refined heuristic algorithm that leverages the power of machine learning to predict an improved initial colouring, allowing for better convergence to the optimal chromatic number. Additionally, we present groundbreaking results in establishing upper bounds on chromatic numbers. Conventional methods for bounding chromatic numbers are often based on the so-called Lovász ϑ function and semidefinite programming. We introduce an original approach that combines spectral techniques with semidefinite relaxation, leading to tighter and more accurate upper bounds for the chromatic number.
Full Text Attachment
