I have a graph, not necessarily connected, that I know for a fact has vertices with degrees at most $3$. I need to find it's chromatic number in polynomial time.
Well then it's just a matter of checking whether the graph is edgeless (if so, then $\chi(G)=1$), or if it's 2-colorable (simple DFS), but I'm stuck at checking if it's $3$-colorable. Brooks theorem states that
For any connected undirected graph G with maximum degree Δ, the chromatic number of G is at most Δ unless G is a clique or an odd cycle, in which case the chromatic number is Δ + 1.
So basically I just have to check if it's a clique or if it's a cycle of odd length (which can be done by DFS also), and If they are not then $\chi(G)=3$, otherwise is $4$, right?
What I'm specifically asking is this. Brooks theorem assumes that $G$ is connected. But what if it's not? Won't I basically get the same thing by treating all components of $G$ separately? Each of them is connected and for each $H \in G$ $Δ_h \leq Δ$, so by Brooks theorem I'm safe if all of the components are not odd cycles, right?