Restating the problem:
Let $G=(V,E)$ be a connected graph with an odd number of vertices, and $\Delta(G)$ is also odd.
describe a linear algorithm that colors $G$, in $\Delta$ colors.
Denote $\vert V\vert =2m + 1,\Delta(G)=2k + 1$.
I'll use the following claim, which is equivalent to the definition of degeneracy of a graph, which I will not proof rigorously:
If $V$ has an ordering such that $$\forall i\in [2m+1]\ \ \vert N_G(v_i)\cap \{v_j\in V\mid j>i\}\vert \leq t$$
Then $\chi(G)\leq t + 1$.
- Where $N_G(v_i)=\{u\in V\mid (u,v)\in E\}$
- $\chi(G)$ is the minimal number of colours one needs to colour $G$
- $[2m+1]:=\{1,2,3,....2m+1\}$
I'll use this claim with $t=2k$
Finding such ordering in linear time
- Pick a vertex $v_1$ with a minimal degree.
- for $i = 1$ to $i = \vert V\vert $: pick a neighbor of $v_i$
- Color the graph using the greedy algorithm, where you color the vertices according to the reverse ordering you found.
Explaining the first and second step
by the Handshaking lemma, not all vertices could have an odd degree.
Therefore $\exists v\in V \ \ s.t\ \ \deg(v)\leq 2k + 1\ \ $ (Since $\Delta(G)$ is odd)
One can repeat this process, Since $N_G(v)>0$ since $G$ is connected, by picking the next vertex in the ordering, to be some vertex in $N_G(v)$ (which is not empty).
When $v_i$ was picked, it had at least one neighbor in the set$[i-1]$.
Since $\deg(v_i)\leq\Delta(G)= 2k+1$, we get $$\vert N_G(v_i)\cap \{v_j\in V\mid j>i\}\vert \leq 2k$$
Explaining the third step (sketch of proof for the claim)
When the greedy algorithm colors the vertex $v_i$, it has at most $2k$ neighbors that were already colored. (Correctness of ordering)
Therefore, the greedy algorithm could pick at least one color, out of the $2k+1$ colors, that was not used, and color $v_i$ with it.
Remark
The statement is wrong when $G$ is not required to be connected.
A counter-example would be $K_4$ with isolated vertex.
