What is the chromatic number of K3, K4, and K5? What is the chromatic number of Kn? The number of ways to color a graph is called its chromatic polynomial. Another way to say this is that it is the number of ways to assign the colors to the vertices. What is the chromatic polynomial of Kz and K4? Generalize this for Kn.
The Correct Answer and Explanation is:
Answer:
- Chromatic Number of K₃: 3
- Chromatic Number of K₄: 4
- Chromatic Number of K₅: 5
- Chromatic Number of Kₙ: n
- Chromatic Polynomial of K₂: P(K2,x)=x(x−1)P(K_2, x) = x(x – 1)
- Chromatic Polynomial of K₄: P(K4,x)=x(x−1)(x−2)(x−3)P(K_4, x) = x(x – 1)(x – 2)(x – 3)
- Chromatic Polynomial of Kₙ: P(Kn,x)=x(x−1)(x−2)⋯(x−n+1)P(K_n, x) = x(x – 1)(x – 2)\cdots(x – n + 1)
Explanation
In graph theory, the chromatic number of a graph is the smallest number of colors needed to color the vertices such that no two adjacent vertices share the same color.
For a complete graph KnK_n, every pair of distinct vertices is connected by an edge. This means each vertex is adjacent to every other vertex. As a result, each vertex must have a unique color to avoid adjacent vertices sharing the same color. Therefore, the chromatic number of KnK_n is exactly n.
- χ(K3)=3\chi(K_3) = 3, because you need three different colors for three fully connected vertices.
- χ(K4)=4\chi(K_4) = 4, one per vertex.
- χ(K5)=5\chi(K_5) = 5, again one per vertex.
Next, the chromatic polynomial P(G,x)P(G, x) of a graph GG counts the number of ways to color the graph with xx colors such that adjacent vertices receive different colors.
For a complete graph KnK_n, the first vertex can be colored in x ways. The second vertex must be a different color, so (x – 1) choices remain. The third vertex must be different from both previous ones, so (x – 2) choices, and so on.
So the chromatic polynomial for KnK_n is: P(Kn,x)=x(x−1)(x−2)⋯(x−n+1)P(K_n, x) = x(x – 1)(x – 2)\cdots(x – n + 1)
This is a falling factorial of length nn, and it only makes sense when x≥nx \geq n; otherwise, the polynomial evaluates to zero or a negative value (which implies zero proper colorings).
For example:
- P(K2,x)=x(x−1)P(K_2, x) = x(x – 1)
- P(K4,x)=x(x−1)(x−2)(x−3)P(K_4, x) = x(x – 1)(x – 2)(x – 3)
Thus, the chromatic polynomial gives insight not only into the number of colors needed but also into how many distinct ways we can color a graph properly using a given number of colors.
