Coloring a graph with odd number of vertices with k (which is close to Δ) colors in linear time

Question

We have an undirected simple connected graph with odd number of vertices. We also know the number k which is actually the closest odd number greater than or equal to Δ. (So if Δ is even, k=Δ+1 else k=Δ.) i.e k is the least odd number that is greater than or equal to degrees of all vertices.

We want to find a linear time algorithm that colors the graph with k colors.

I am very new to graph coloring algorithms. I know that a greedy algorithm is actually linear time and can color the graph with Δ+1. But I can't guarantee I can color it with k=Δ when Δ is odd. Also, we probably should use all the information the question gives us. i.e using odd number of vertices somehow, but greedy algorithm don't use this extra information.

How can I solve this?

Answer 1

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$.

1. Where $N_G(v_i)=\{u\in V\mid (u,v)\in E\}$
2. $\chi(G)$ is the minimal number of colours one needs to colour $G$
3. $[2m+1]:=\{1,2,3,....2m+1\}$

I'll use this claim with $t=2k$

Finding such ordering in linear time

1. Pick a vertex $v_1$ with a minimal degree.
2. for $i = 1$ to $i = \vert V\vert $: pick a neighbor of $v_i$
3. 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.