I am looking to derive an algorithm that finds, for every connected graph $G$ that is neither complete nor an odd cycle, a $\Delta(G)$-colouring in time $O(m+n)$.
When we proved Brooks' theorem we used the depth first search (DFS) algorithm which will be helpful to prove this but I am not quite sure how to proceed with this problem.
Any tip or material about time complexity of Brooks' theorem would be much appreciated