For a graph G, the chromatic polynomial P(G, k) counts the number of proper vertex colorings...

 

Transcribed Image Text:

For a graph G, the chromatic polynomial P(G, k) counts the number of proper vertex colorings of G with k colors. In other words, P(G, k) is the number of ways to color the vertices of G using k colors in such a way that no two adjacent vertices have the same color. For example, to color the cycle C3 on 3 vertices {1,2,3} using k colors, there are k choices for the color of vertex 1. Then, since vertex 2 is adjacent to vertex 1, there are k-1 choices for the color of vertex 2, since vertex 2 can be colored with any of the k colors except the color used for vertex 1. Finally, since vertex 3 is adjacent to both vertices 1 and 2, there are k-2 choices for the color of vertex 3. Thus, P(C3, k) k(k-1)(k − 2) = k³-3k² +2k = (k-1)³ - (k-1). Find the chromatic polynomial of C4. For a graph G, the chromatic polynomial P(G, k) counts the number of proper vertex colorings of G with k colors. In other words, P(G, k) is the number of ways to color the vertices of G using k colors in such a way that no two adjacent vertices have the same color. For example, to color the cycle C3 on 3 vertices {1,2,3} using k colors, there are k choices for the color of vertex 1. Then, since vertex 2 is adjacent to vertex 1, there are k-1 choices for the color of vertex 2, since vertex 2 can be colored with any of the k colors except the color used for vertex 1. Finally, since vertex 3 is adjacent to both vertices 1 and 2, there are k-2 choices for the color of vertex 3. Thus, P(C3, k) k(k-1)(k − 2) = k³-3k² +2k = (k-1)³ - (k-1). Find the chromatic polynomial of C4.