raph Theory
Exam 3
April 20, 2013
Problem Points Score
1 16
2 16
3 16
4 16
5 12
6 12
7 12
Total 1001. (16 points) Prove that the chromatic number of a graph is the maximum
of the chromatic numbers of its bloc
...
raph Theory
Exam 3
April 20, 2013
Problem Points Score
1 16
2 16
3 16
4 16
5 12
6 12
7 12
Total 1001. (16 points) Prove that the chromatic number of a graph is the maximum
of the chromatic numbers of its blocks.
It is easy to see that the chromatic number is at least the maximum of the
chromatic numbers of the blocks, because any r-coloring of the graph may
be restricted to an r-coloring of a block of the graph.
For the remainder of the proof, let r(G) be the maximum of the chromatic
numbers of the blocks of G.
To show that the chromatic number is exactly the maximum, we construct
a r(G)-coloring. The block graph is a tree, from a previous homework, so
we prove by induction on the number of blocks.
In the base case, the graph has only one block, and this block must be the
entire graph (as any vertex not in the block is a connected subgraph without
a cutvertex, so either another block or a subgraph of a block). Then, clearly
r(G) = χ(G) from the definition of r(G).
For a graph with multiple blocks, consider a block B that is a leaf in the block
graph (the leaves of the block graphs are not cutvertices because cutvertices
must be contained in the the blocks of at least two of their neighbors that
are seperated upon deletion of the cutvertex). This block has exactly one
cutvertex, v, and contains other vertices (by minimality), so we may delete
all of the block except the cutvertex, and get a graph with fewer blocks,
G−(B −v). From the induction hypothesis we get a coloring of G−(B −v)
that uses at most r(G − (B − v)) ≤ r(G) colors. Also, from the induction
hypothesis, these is a coloring of B that uses at most r(B) ≤ r(G) colors.
We take the coloring of B and exchange the color it gives to v with the color
given to v in the coloring of G−(B −v). Combining the exchanged coloring
of B with the coloring of G − (B − v) gives a coloring of G
[Show More]