How can we count different coloring in 2 cycle with one edge in common

Question

There is a question that asked what is the counts of different coloring in $C_5$ and $C_6$ when it has one edge in common: I have used fundamental reduction in cycles in order to get a recursive formula (I know there is a closed formula for that too), but when i try use the same in this particular question, it becomes very complicated. How can I find a formula for this kind of graph? Im looking for Chromatic Polynomial.

Answer 1

Let's first find a formula for a "mouse graph" ($C_n$ with a path $P_m$ attached)

This is easy with induction and the fundamental d-c. We know that for $n$-cycle the chromatic polynomial is $C_n(x) = (x-1)^n+(-1)^n(x-1)$ and we get that for the mouse it is

$$M_{n,m}(x) = (x-1)^m C_n(x)$$

Now for the graph in question. Let's denote the chromatic polynomial by $P_{n,m}$, where $n$ is the number of nodes in the first cycle and $m$ is the extra nodes in the second. So what we want is $P_{6, 3}$.

When we use deletion-contraction on the first edge that comes out on the second cycle, we get the recursion (and the basecase $P_{n,0} (x) = C_n(x)$)

$$P_{n,m}(x) = M_{n,m}(x) - P_{n,m-1}(x)\\ = M_{n,m}(x) - M_{n,m-1}(x) + P_{n,m-2}(x)\\ = \dots =\\ = \sum_{j=0}^m (-1)^j M_{n,m-j}(x) = C_{n}(x)\sum_{j=0}^m (-1)^j (x-1)^{m-j}\\ = C_{n}(x)(-1)^m\sum_{j=0}^m (1-x)^{j} \\ = C_n(x)(-1)^m\frac{1-(1-x)^{m+1}}{x}\\ = C_n(x)\frac{(x-1)^{m+1} + (-1)^m}{x}$$

You can check the answer with the following SAGE-code:

R.<x> = QQ['x']

def c(n):
    return x if n==1 else (x-1)**n + (-1)**n*(x-1)

def makeGraph(n, m):
    N = n+m
    g = Graph(N)
    for i in range(N): g.add_edge(i, (i+1)%N)
    if n>1 and m>1: g.add_edge(0, n-1)
    return g

def getFormula(n, m):
    #TODO doesn't work for n==1 or m==1
    p = c(n)*(-1)**m*(1-(1-x)**(m+1))/x
    return p


for n in range(1, 10):
    for m in range(1, 10):
        p = makeGraph(n,m).chromatic_polynomial()
        pFormula = getFormula(n,m)
        if p != pFormula:
            print("Wrong formula with %d, %d" %(n,m))
            print (p)
            print (pFormula)

EDIT The formula doesn't work for the cases where $n=1$ or $m=1$.

Answer 2

Wikipedia gives the chromatic polynomial of the cycle graph $C_n$ as $(x-1)^n+(-1)^n(x-1)$. In your graph we can choose the first point that is common to the cycles in $x$ ways and the other point in common in $x-1$ ways. That choice is common to the two cycles, then we can complete each in any way we want, so the chromatic polynomial is $$\frac {\left((x-1)^6+(-1)^6(x-1)\right)\left((x-1)^5+(-1)^5(x-1)\right)}{x(x-1)}=\\x^9 - 10 x^8 + 45 x^7 - 120 x^6 + 209 x^5 - 245 x^4 + 190 x^3 - 90 x^2 + 20 x=\\(x - 2) (x - 1) x (x^2 - 2 x + 2) (x^4 - 5 x^3 + 10 x^2 - 10 x + 5)$$ where I got Alpha to do the simplification. The presence of $(x-1)(x-2)$ and no $(x-3)$ says the chromatic number is $3$.