# Prove that the chromatic number of a graph is the same as the maximum of the chromatic numbers its blocks.

Here's the statement to be proved:

The chromatic number of a graph is the same as the maximum chromatic number of its blocks.

Here's what I think. We consider the graph $G$ with chromatic number $\chi(G)=k$. Let $\chi(B)$ be the maximum chromatic number of a block of $G$. Now, clearly $\chi(B) \leq k,$ since a block is a subgraph of $G.$ This would tell me that every individual block could be colored with at most $k$ colors.

Now, any two blocks share at most one vertex, so intuitively it would make sense that we could find a proper coloration for $G$ with at most $k$ colors, by picking the color of the common vertices in a clever way. But how can I prove this?

Any help is appreciated.

• What is your definition of block? "A subgraph with as many edges as possible and no cut vertex (a vertex whose removal disconnects the subgraph)" ? – Jack D'Aurizio Apr 16 '18 at 15:35
• @JackD'Aurizio My definition of a block is a maximal nonseparable subgraph of a graph $G$. So yes, basically what you just said. – Thomas Bladt Apr 16 '18 at 15:44
• Years ago, I took a course in combinatorial algorithms where the book stated that this was obvious, and I don't think I ever figured out why. Thanks for asking this question. +1 – saulspatz Apr 16 '18 at 16:56
• @saulspatz I'm glad my question has also helped others! – Thomas Bladt Apr 16 '18 at 18:15

The block decomposition of a graph leads to a tree. Assume that all the blocks of $G$ have been colored but two blocks $B_1,B_2$ do not agree about the coloring of their common vertex. Then by rotating/replacing the colors in one of the two blocks we may resolve such issue. Due to the tree-structure of the block decomposition, we may pick a block as "root" and resolve all the color-conflicts, proceeding from the root to the leaves and fixing the colors of the children blocks each time.
• @ThomasBladt: color $B_1,B_2,B_3$. Rotate the colors of $B_2$ in such a way that $B_1,B_2$ agree on the common vertex. Then rotate the colors of $B_3$ in such a way that $B_2,B_3$ agree on the common vertex. Top-down. – Jack D'Aurizio Apr 16 '18 at 18:46