arXiv:2605.13299 · v2
Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
摘要
A strong conflict-free vertex connection coloring of a graph is a graph coloring for which, for every two distinct vertices of the graph, there exists a shortest path between them in which some color in said coloring appears only once. The strong conflict-free vertex connection number, denoted by $\operatorname{svcfc}(G)$, is the number of colors in the strong conflict-free vertex connection coloring with the smallest amount of colors out of all such colorings of $G$. We study the problem of deciding whether this number is at most some threshold together with the parameter twin cover. Our first result is that when we have given $(G,k)$ in which $k$ is some target number of colors and given some twin cover $X$ of $G$ which is of size $t$, there is a polynomial time reduction to an equivalent instance which has at most $\max\{2,t+k2^t\}$ vertices. This result allows us to give a kernel for Strong CFVC Number which is parameterized by $\operatorname{tc}(G)+k$, which implies that Strong CFVC Number is FPT w.r.t. the twin-cover number of $G$ so long as $k$ is fixed. Our second result is that if $G$ is a connected graph for which there exists a twin cover of size $t$, then $χ(G)\le \operatorname{svcfc}(G)\le χ(G)+t$. Our last result is an an exact expression for the chromatic number of graphs whose twin cover number is bounded. Namely, we show that for every proper coloring $\varphi$ of $G[X]$, the minimum number of colors needed to extend $\varphi$ to all of $G$ is $K_\varphi=\max_{S\subseteq X}(|\varphi(S)|+m(S))$, and hence $χ(G)=\min_{\varphi\text{ proper on }G[X]} K_\varphi$. Our results indicate that twin cover is a meaningful parameter in the context of strong conflict-free vertex-connection, and show that once we have a fixed twin cover, the only difficulty left is in some additive threshold above the chromatic number.
作者备注：This version strengthens the vertex bound in the kernelization from $\max\{2,t+(t+1)k2^{t+k-1}\}$ to $\max\{2,t+k2^t\}$, as well as streamlines the exposition
期刊信息：32nd International Computing and Combinatorics Conference (COCOON 2026), Lecture Notes in Computer Science, vol. 16835, pp. 397-408, Springer (2027)