Q7Discrete Mathematics Structure

Question

Find the chromatic polynomial, chromatic number and number of ways of proper coloring with minimum colors of the given graph : a square with vertices a,b,c,d and a diagonal edge.

Answer 1

The graph is a square with a diagonal, which forms two triangles sharing an edge. Decomposition: Two triangles $K_{3}$ joined at an edge $K_{2}$ .

Using the glueing formula: $P (G, k) = \frac{P ( K _{3} , k ) P ( K _{3} , k )}{P ( K _{2} , k )} = \frac{[ k ( k - 1 ) ( k - 2 ) ] ^{2}}{k ( k - 1 )} = k (k - 1) (k - 2)^{2}$ .

Chromatic Number $χ (G)$ : 3, as the graph contains $K_{3}$ and is not 2-colorable (due to triangles).

Q7Discrete Mathematics Structure

Question

Answer