Chapter 12, Problem 1E

To determine

To prove: The isomorphic graphs have the same chromatic number and the chromatic polynomial.

Explanation of Solution

Definition used:

Chromatic number:

Let $G=\left(V,E\right)$ be a graph. A vertex coloring of G is an assignment of a color to each of the vertices of G in such a way that adjacent vertices are assigned different colors. If the colors are chosen from a set of k colors, then the vertex-coloring is called k-coloring. If G has a k-coloring, then G is said to be k-colorable. The smallest k, such that G is k-colorable, is called the chromatic number of G, denoted by $\chi \left(G\right)$.

Chromatic polynomial:

For each nonnegative integer k, the number of k-colorings of the vertices of a graph G is denoted by $p_G\left(k\right)$. Also, $p_G\left(k\right)$ is always a polynomial function of k and is called the chromatic polynomial of the graph G.

Description:

Suppose that, $G_1=\left(V_1,E_1\right)\text{ and }{G}_2=\left(V_2,E_2\right)$ be two isomorphic graphs and the isomorphism be defined as, $f:V_1\to V_2$.

Let $c:V_1\to n=\left\{1,2,\dots ,n\right\}$ be a vertex coloring of the graph $G_1$ using n colors.

By the isomorphism defined, a vertex u in $V_1$ is isomorphic to a vertex v in $V_2$.

That is, the vertex v in $V_2$ receives the same color the vertex u receives in $V_1$.

Then, $c\circ f^{-1}:V_2\to n=\left\{1,2,\dots ,n\right\}$ will be a vertex coloring of the graph $G_2$ using n colors.

Similarly, the coloring in $G_2$ can also be transformed to coloring in $G_1$.

If $c^{\prime }$ is a coloring into $G_2$, then the coloring into $G_1$ will be $c^{\prime }\circ f$.

Thus, the isomorphism condition implies that the colorings onto $G_1$ will result to the colorings onto $G_2$ using the same number of colors and vice versa.

That is, the operations are inverse of each other and thus obtaining a bijection of coloring of the graphs $G_1\text{ and }{G}_2$ using the same colors.

By the above mentioned definitions, the chromatic number and chromatic colorings depends only on the number of colorings. Here, both the graphs have same colorings.

Therefore, the isomorphic graphs have the same chromatic number and the chromatic polynomial.