On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs

NEW

Problem: For a finite simple graph $G$, let $N[v]$ be the closed neighbourhood of $v$. For a vertex-coloring $c$, write

A coloring is adjacent-vertex closed distinguishing if $C_c[u]\ne C_c[v]$ for every edge $uv$. Let $\operatorname{dis}[G]$ be the minimum number of colors in such a coloring, and let $\operatorname{dis}_{\ell}[G]$ be the corresponding list version. The problem asks whether, for every positive integer $t$, there is a bipartite graph $G$ with

The same construction also works if the paper’s convention requires the coloring to be proper.

Result: Yes.

Fix $t\ge1$, and put $q=t+3$. Let $\mathcal F$ be the family of all $q$-subsets of a set $P$ of size $2q-1$. Let $H=K_{\mathcal F,\mathcal F}$, with one vertex $a_F$ in the left part and one vertex $b_F$ in the right part for each $F\in\mathcal F$.

Give both $a_F$ and $b_F$ the list $F$. There is no proper list-coloring of $H$: if $S$ is the set of colors used on the left part, then every $F\in\mathcal F$ meets $S$, while every $F\in\mathcal F$ must also meet $P\setminus S$, since the right part cannot use any color already used on the left. Thus both $|S|\le q-1$ and $|P\setminus S|\le q-1$, contradicting $|P|=2q-1$. Hence $\chi_\ell(H)>q$.

Now form a bipartite graph $G$ by replacing every edge $xy$ of $H$, with $x$ in the left part and $y$ in the right part, by a path

First, $\operatorname{dis}[G]\le4$: color the original left vertices by $1$, the original right vertices by $2$, all $p_{xy}$ by $3$, and all $r_{xy}$ by $4$. Then along each path,

so every adjacent pair is distinguished. This coloring is also proper.

Second, $\operatorname{dis}_{\ell}[G]>q$. Extend the above bad $q$-list assignment on the original vertices of $H$ to $G$ by giving every subdivision vertex the same $q$-element list $D$, disjoint from $P$. Suppose a closed distinguishing list-coloring existed. For an original edge $xy$ of $H$, consider the middle edge $p_{xy}r_{xy}$. Its two closed-neighbourhood color sets are

Since $c(x),c(y)\in P$ and $c(p_{xy}),c(r_{xy})\in D$, these two sets differ only if $c(x)\ne c(y)$. Hence the restriction of $c$ to the original vertices is a proper list-coloring of $H$, impossible. Therefore $\operatorname{dis}_{\ell}[G]\ge q+1=t+4$.

Thus

Citation: No exact prior resolution is used here. The list-coloring obstruction is the standard Erdős–Rubin–Taylor phenomenon that complete bipartite graphs have unbounded choice number.