# A modified 4-coloring problem

Given a graph $$G$$ with vertex set $$V$$ and edge set $$E$$, the standard coloring problem is to ask the number of ways that the graph can be colored with $$k$$ colors such that no adjacent vertices have the same color. This is given by the chromatic polynomial $$P(G,k)$$ with the following recurrence relationship: $$\forall e \in E \quad P(G-e,k) = P(G/e,k) + P(G,k)$$ where $$G-e$$ means the removal of edge $$e$$, and $$G/e$$ denotes the contraction of edge $$e$$.

We now consider a modified version of this problem, where we assign every vertex an element in $$\mathbb{Z}_4$$ such that no adjacent vertices can differ by $$2 (\mod 4)$$, but they can now be the same or differ by $$1$$. In general, is there any recurrence relations one can write down? And furthermore, is there a polynomial time algorithm for evaluating the number of valid "coloring" configurations given any graph $$G$$ (which I will denote as $$C'(G)$$ from here on) for this modified coloring problem. Note that trivially, $$\chi'(G) = 1$$ and $$C'(G) \geq 1$$ by just coloring the entire graph with a single color.

A question of my direct interest is whether there is a positive lower bound for the ratio between $$C'(G/e)$$ and $$C'(G-e)$$ for the modified coloring scheme, or whether the following is true $$\exists m > 0, \quad \min_G\min_{e\in E} \frac{C'(G/e)}{C'(G-e)}\geq m$$ as we take the limit $$|V|\to \infty$$. In other words, once two vertices are merged into a single vertex, what fraction of the valid $$\mathbb{Z}_4$$ configurations of the original graph are we left with? Is there such bound at least for the origianl 4-coloring problem?