Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911680166887424 |
|---|---|
| author | German, Samuel |
| author_facet | German, Samuel |
| contents | 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 $φ$ of $G[X]$, the minimum number of colors needed to extend $φ$ to all of $G$ is $K_φ=\max_{S\subseteq X}(|φ(S)|+m(S))$, and hence $χ(G)=\min_{φ\text{ proper on }G[X]} K_φ$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_13299 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds German, Samuel Discrete Mathematics Data Structures and Algorithms 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 $φ$ of $G[X]$, the minimum number of colors needed to extend $φ$ to all of $G$ is $K_φ=\max_{S\subseteq X}(|φ(S)|+m(S))$, and hence $χ(G)=\min_{φ\text{ proper on }G[X]} K_φ$. 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. |
| title | Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds |
| topic | Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.13299 |