Show that the chromatic number of a Series Parallel graph is at most 3

Question

Although it is "well known" that a (simple) series parallel graph has chromatic number at most 3, I cannot seem to find a proof of this statement anywhere.

Does anyone know how to prove the statement?

It may be related to the fact that series parallel graphs are K4 minor free.

Answer 1

Every series-parallel graph (SPG) may be coloured with at most $3$ colours such that their source and sink are coloured differently (a P-colouring). This is clearly true for the base case, a single edge.

Suppose we have two P-coloured SPGs; the first's source and sink are coloured with colours $a$ and $b$, the second's $c$ and $d$ respectively. By permuting colours

• we can make $b=c$ and $a\ne d$, whereby we can form a P-coloured series composition of the two graphs
• we can make $a=c$ and $b=d$, whereby we can form a P-coloured parallel composition of the two graphs

Since all SPGs are formed by series and parallel compositions from the single edge, this shows by induction that all SPGs have a P-colouring, i.e. a $3$-colouring.