3
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ What you should worry about is that one of the components might be a $4$-clique. As a corollary of Brooks's theorem, if $G$ has maximum degree $\le3$ and contains no $K_4$, then $G$ is $3$-colorable. $\endgroup$
    – bof
    Sep 27, 2019 at 1:06

1 Answer 1

1
$\begingroup$

Your reasoning is correct. Theorems about chromatic number are stated in terms of connected graphs since the disconnected case is not interesting. Indeed, if $G$ has connected components $G_1,\ldots,G_n$ then $$\chi(G) = \rm{max}(G_1,\ldots,G_n).$$

So the fact that Brook's theorem speaks about connected graphs is probably to avoid the technicalities of stating the result for connected components.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.