Edward Mirco
Solving Graph Colouring Problems via Convex Optimization
We introduce a novel reformulation of the graph colouring problem (GCP), which is the problem of assigning labels or colours to the vertices of a graph such that no two adjacent vertices are assigned the same colour. From this we derive a convex optimization problem that finds a colouring of a given graph with the minimal possible number of colours used; an optimal colour of the graph. We aim to implement existing efficient convex optimization algorithms to this problem, identify and apply graph decomposition techniques to further improve performance, and identify what properties of a graph might make it more susceptible to this approach.
Edward Mirco
Curtin University
Edward began a BSc with a major in Physics in 2022 at Curtin University, and has participated in a scholarship research opportunity in computational quantum collision theory to be applied in international fusion energy experimental collaborations. His current research is in the field of graph theory and combinatorics, and he is to graduate at the end of 2025, and pursue postgraduate studies in pure and applied mathematics.
