1
$\begingroup$

How can I prove that any graph of treewidth $w$ can be vertex colored with $w+1$ colors?

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $G=(V,E)$ be our graph. If $G$ has treewidth $w$, it has a tree decomposition $T$, with vertex set $\{X_1, X_2, \dots, X_k\}$. The "vertices" of $T$ are subsets of $V$ such that every set $X_i$ has at most $w+1$ vertices (i.e, the width of $T$ is at most $w$).

We colour the vertices of $G$ as follows (the pictures show a tree decomposition of a graph with treewidth $2$).

Step 1: Give each vertex of $X_1$ its own colour (we have used at most $w+1$ colours so far).

enter image description here

Step 2: Now consider all the sets $X_j$ that are adjacent to $X_1$ in $T$. Each $X_j$ has some vertices in common with $X_1$, which are already coloured. If $v$ is a vertex of $X_j-X_1$, then it is not adjacent to any vertex if $X_1-X_j$, since $T$ is a tree decomposition (basically, in $X_j$, if $v$ is not yet coloured, we can give it any colour we like that does not appear on another vertex of $X_j$). Thus there is at least one of the first $w+1$ colours that we can give to $v$. Going one by one through the neighbors of $X_1$, we can colour all their vertices in this way.

enter image description here

Step 3: We now look at the sets distance $2$ from $X_1$ in the tree $T$. We do the same thing as in step 1, colouring the vertices that are not yet coloured with whatever colours are left over for them.

enter image description here

Repeat this process until all vertices are coloured, giving $G$ a $w+1$ colouring and completing the proof.


You can also use the fact that the treewidth is the clique number $\omega$ of a chordal completion of $G$ minus $1$, and the fact that chordal graphs are perfect (so $\omega = \chi$), to give a one line proof (that requires knowing two big theorems).

$\endgroup$
2
  • $\begingroup$ I like your diagrams :) $\endgroup$ Oct 18, 2020 at 21:15
  • $\begingroup$ Thanks, appreciated ^^ $\endgroup$ Oct 18, 2020 at 21:15

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.