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
    Commented Sep 27, 2019 at 1:06

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .