Question

Write down the chromatic polynomials of (i) the complete graph \(K_{7}\) (ii) the complete bipartite graph \(K_{1,6^{*}}\) In how many ways can these graphs be coloured with ten colours?

Short answer

The chromatic polynomials of \(K_{7}\) and \(K_{1,6^{*}}\) are \(k*(k-1)^6\) respectively. Both \(K_{7}\) and \(K_{1,6^{*}}\) can be colored in \(10*9^6\) ways in ten colors.

Step-by-step solution

Chromatic polynomial of a complete graph

The chromatic polynomial of any complete graph \(K_n\) is given by \( P(K_n, k) = k*(k-1)^{n-1}\). Given the complete graph \(K_{7}\), to find the chromatic polynomial, plug \(n = 7\) into the formula. This gives us \( P(K_7, k) = k*(k-1)^6\).

Evaluate chromatic polynomial at \(k = 10\)

Calculate the number of ways the complete graph \(K_{7}\) can be colored with 10 colors by evaluating the chromatic polynomial at \(k = 10\). This gives us \( P(K_7, 10) = 10*(10 - 1)^6 = 10 * 9^6\).

Chromatic polynomial of a complete bipartite graph

The chromatic polynomial of a complete bipartite graph \(K_{1,6^{*}}\) is \(P(K_{1,6^{*}}, k) = k*(k-1)^6\) because from every vertex in the first subset there is an edge to every vertex in the second subset but none between vertices within a set. There is one vertex in the first subset and six vertices in the second subset in this case.

Evaluate chromatic polynomial at \(k = 10\)

Calculate the number of ways the complete bipartite graph \(K_{1,6^{*}}\) can be colored with 10 colors by evaluating chromatic polynomial at \(k=10\). This gives \(P(K_{1,6^{*}},10) = 10*9^6\).

Compare the number of ways each graph can be colored

Comparing steps 2 and 4, notice that the number of ways in which the graphs \(K_7\) and \(K_{1,6^{*}}\) can be colored with 10 colors is the same.

Key concepts

Complete Graph

A complete graph, often denoted as \(K_n\), is a type of graph where there is a unique edge between every pair of vertices. This means each vertex is connected to every other vertex directly.
Complete graphs are one of the simplest and most interconnected types of graphs. If you imagine five points on the perimeter of a circle, and each point is connected to every other point with a line, you've visualized a complete graph, specifically \(K_5\).

• The most notable feature is that it has the maximum possible number of edges for \(n\) vertices.
• The number of edges in a complete graph \(K_n\) is \(\frac{n(n-1)}{2}\).
• Every pair of vertices has a direct connection, leading to its complete nature.

The chromatic polynomial for a complete graph \(K_n\) is \(P(K_n, k) = k(k-1)^{n-1}\). This equation represents how we determine the number of ways to color the graph such that no two adjacent vertices share the same color.
For example, for a complete graph with 7 vertices \(K_7\), and 10 colors, this would be \(10 * 9^6\), representing the different ways you could color the graph.

Complete Bipartite Graph

A complete bipartite graph, denoted as \(K_{m,n}\), consists of two distinct sets of vertices.
Every vertex in the first set is connected to every vertex in the second set, but no vertices within the same set are connected. Think of it like two separate groups of dots, where every dot in one group connects to all dots in the other group, but nothing within its own group.

• Graphically, this creates two clusters of connected vertices, creating a bridge between the two sets.
• There are no edges between vertices in the same set, emphasizing the partition between the sets.

For example, in the graph \(K_{1,6}\), there is one vertex in the first subset and six vertices in the second subset. The chromatic polynomial for a complete bipartite graph is the same as that for a complete graph in this setup: \(P(K_{m,n}, k) = k(k-1)^6\).
This accounts for the lack of internal edge connections within the same set, maintaining the color-diversity across the subsets.

Graph Coloring

Graph coloring is an essential concept in graph theory, involving the assignment of colors to the vertices of a graph.
The goal is to ensure that no two adjacent vertices share the same color. This concept finds numerous applications in scheduling, allocating resources, and solving puzzles like the famous "four-color theorem" in map coloring.

• Chromatic number is the smallest number of colors needed to color a graph in this way.
• Chromatic polynomial provides a way to count the number of ways a graph can be colored, given \(k\) colors.

For instance, using the chromatic polynomial, you can determine how many ways you can color a specific graph like a complete graph or a bipartite graph with a given number of colors, such as 10 in our previous exercise.
Understanding graph coloring and using chromatic polynomials help solve complex problems involving networks, ensuring optimal resource allocation with minimal color use.