11
$\begingroup$

Consider a square, ABCD. Intuitively it seemed to me that its chromatic polynomial is $\lambda(\lambda - 1)(\lambda - 1)(\lambda - 2)$ where there are $\lambda$ colours available..

That is there are $\lambda$ ways in which a colour for A can be picked, there are $\lambda - 1$ ways for colours for B and D to be picked(B and D are adjacent to A) and $\lambda - 2$ ways for colours for C to be picked.

However using the decomposition theorem (slide 47, Example 11.33) and decomposing the square into a path of length 3 and a triangle, shows that my initial reasoning is wrong.

Could you tell me where I am going wrong with my thinking.

$\endgroup$
8
$\begingroup$

You must remember that the vertices diagonal from one another can be colored the same! Your formula does not take that into account. We can find the chromatic number of a graph via the inclusion-exclusion principle. It is a very general counting technique that allows us to count complex structures, if we can prove certain bounds on certain subsets.

The main idea is that we count all possible ways some property happens. Then we remove some "bad" items. However, we may have removed too much, and need to add back some "good" items. This goes back and forth until we've gone through all subsets.

Inclusion-exclusion principle tells us that given some ground set $|X|=n$, the number of elements of $X$ which lie in none of the subsets $A_i$ is $$ \sum_{I \subseteq [n]} (-1)^{|I|}|A_I| \text{, where } \\ I \text{ is the set of indices in } X \text{ and } A_I = \bigcap_{i \in I} A_i$$

Let $\lambda$ be the number of colors, and let $X$ be the set of all possible colorings (i.e., $|X| = \lambda^4$), and let $$A_{e} = \{\text{coloring} : e=(i,j) \in E, \text{color}(i) = \text{color}(j) \}$$

Before we get our final polynomial, we need to count the size of our sets $A_{e}$, and the size of all intersecting subsets.

Observe that $|A_{12}| = |A_{23}| = |A_{34}| = |A_{41}| = \lambda^3$. This is due to the fact that we are just coloring $G$ but always picking the same colors for neighboring vertices. Going forward we have,

$|A_{12} \cap A_{23} | = |A_{23} \cap A_{34} | = |A_{34} \cap A_{41}| = |A_{41} \cap A_{12}| = |A_{12} \cap A_{34}| = |A_{41} \cap A_{23}| = \lambda^2$

I'm not going to list each 3-set, but they all have the same count. $|A_e \cap A_{e'} \cap A_{e''}| = \lambda$. And Finally, $|A_{12} \cap A_{23} \cap A_{34} \cap A_{41}| = \lambda$. Now lets collect our terms and add up.

$$\lambda^4 - 4\lambda^3 + 6\lambda^2 - 4\lambda + \lambda = \lambda^4 - 4\lambda^3 + 6\lambda^2 - 3\lambda$$

Now counting with inclusion-exclusion for this problem wasn't so bad because we had a simple 4-cycle. If the graph had more structure it would quickly get annoying to figure out each intersection size for all possible intersections.

$\endgroup$
2
$\begingroup$

The answer by Nicholas above and this one helped me see the flaw in my thinking. I thought of elaborating more specifically upon Nicholas',

You must remember that the vertices diagonal from one another can be colored the same

and also obtain the chromatic polynomial by adjusting for my wrong reasoning.

I had initially figured that there are $\lambda - 2$ ways of picking colors for C. The "-2" accounted for the colors being different from that of B and D. What I did not think about is that B and D can have the same colors in which case there would be just $\lambda - 1$ way of picking colors for C. Thus

$P(ABCD, \lambda)$ = Number of ways of properly coloring ABCD when B and D are of the same color + Number of ways of properly coloring ABCD when B and D are colored differently
= $λ(λ−1)(1)(λ−1) + λ(λ−1)(λ−2)(λ−2)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.