DisMat UE 11

ex11-0.pdf

1.

Chromatic Polynomial

Transclude of dismat-ue-11-1.excalidraw

$$V_{n-1}(G)=\left(\genfrac{}{}{0ex}{}{n}{2}\right)-|E(G)|$$ $$P(G,t)=\sum _{k\ge 1}{V}_k(G)t(t-1)...(t-k+1)$$

Not connected:

$$P(N_2,t)=t^2$$

Fully connected:

$$P(K_n,t)=t(t-1)(t-2)...(t-n+1)$$

Every pair can either be one or two colors. -> $2^m$

$$P(K_{2,2,..,2},t)=\sum _{i=0}^{2^m-1}P(K_{m+i},t)$$

2.

Propertys of Trees

$$|E(G)|=|V(G)|-1$$

No Child can have the color of the parent.
But all the Children can have the same color.
-> Two Colors are enough

• Pick root Node
• Chose a color -> t
• Go into a child
• This child can choose alle color expect the of the parent -> $t-1$
• Go over all uncolored children -> $n-1$

Suppose $G$ is not a tree:

Case 1: G has a Cycle
There must come a point where a vertecy has more than one already colored neigbor.
Those two vertecies can have different colors because the color of a child is not futher restrainted. In this case the vertex could only choose from $t-2$ colors.

Case 2: G is not connected
There would be two root Vertcies

Transclude of dismat-ue-11-2.excalidraw