# Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds

Preprint · Samuel German

- Archive id: arxiv:2605.13299
- Published: 2026-05-13
- Venue: 32nd International Computing and Combinatorics Conference (COCOON 2026), Lecture Notes in Computer Science, vol. 16835, pp. 397-408, Springer (2027)
- DOI: https://doi.org/10.1007/978-981-92-3309-0_30
- arXiv: https://arxiv.org/abs/2605.13299
- Source URL: https://arxiv.org/abs/2605.13299
- PDF: https://arxiv.org/pdf/2605.13299
- Provenance: arxiv

## Abstract

A vertex-coloring of a connected graph $G$ is a strong conflict-free vertex-connection coloring if every two distinct vertices are joined by a shortest path on which some color appears exactly once. The minimum number of colors in such a coloring is the strong conflict-free vertex-connection number $\\operatorname{svcfc}(G)$. We study this problem under the parameter twin cover. Let $X$ be a twin cover of $G$ of size $t$, and let $k$ be the target number of colors. In our first result, given $(G,k)$ together with a twin cover $X$, we reduce in polynomial time to an equivalent annotated instance on at most $\\max\\{2,t+(t+1)k2^{t+k-1}\\}$ vertices. Hence the annotated version of Strong CFVC Number, in which a twin cover is supplied as part of the input, is fixed-parameter tractable parameterized by $t+k$. Using this bound, we then obtain a kernel parameterized by $\\operatorname{tc}(G)+k$; in particular, for every fixed $k$, the problem is fixed-parameter tractable parameterized by the twin-cover number alone. In our second result, we prove every connected graph $G$ with twin cover $X$ of size $t$ satisfies $χ(G)\\le \\operatorname{svcfc}(G)\\le χ(G)+t$. More generally, if $Y\\subseteq X$ intersects every shortest path of length at least $3$, then $\\operatorname{svcfc}(G)\\le χ(G)+\|Y\|$. We also derive an exact expression for the chromatic number on graphs of bounded twin-cover number: 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 provide the first evidence that twin cover is a useful parameter for strong conflict-free vertex-connection and show that, once a twin cover is fixed, the remaining difficulty is concentrated in a bounded additive gap above the chromatic number.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.