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?



You must log in to answer this question.

Browse other questions tagged .