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.

  • $\begingroup$ 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)" ? $\endgroup$ – Jack D'Aurizio Apr 16 '18 at 15:35
  • $\begingroup$ @JackD'Aurizio My definition of a block is a maximal nonseparable subgraph of a graph $G$. So yes, basically what you just said. $\endgroup$ – Thomas Bladt Apr 16 '18 at 15:44
  • 1
    $\begingroup$ 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 $\endgroup$ – saulspatz Apr 16 '18 at 16:56
  • $\begingroup$ @saulspatz I'm glad my question has also helped others! $\endgroup$ – 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.

  • $\begingroup$ +1 Would it also work to just color the blocks top-down in the tree? If I'm not mistaken, no conflicts would arise. $\endgroup$ – saulspatz Apr 16 '18 at 16:38
  • $\begingroup$ @saulspatz: oh, sure, that is clearly more algorithmically efficient than coloring first and fixing it later. $\endgroup$ – Jack D'Aurizio Apr 16 '18 at 16:39
  • $\begingroup$ Thank you for you answer. What is still not so clear to me is how we can assure that we will always be able to resolve the possible color conflicts that arise, could you tell me why that is? $\endgroup$ – Thomas Bladt Apr 16 '18 at 18:14
  • 1
    $\begingroup$ @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. $\endgroup$ – Jack D'Aurizio Apr 16 '18 at 18:46
  • 1
    $\begingroup$ @JackD'Aurizio Oh, now I get it! That's what you meant when you said pick a root block. Thank you very much! $\endgroup$ – Thomas Bladt Apr 16 '18 at 18:50

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.