2026/05/13 by Samuel German · 1 voice
Computer Science · #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.2605.13299
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 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)k2t+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 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)≤ svcfc(G)≤ χ(G)+t. More generally, if Y⊆ X intersects every shortest path of length at least 3, then svcfc(G)≤ χ(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φ=maxS⊆ X(|φ(S)|+m(S)), and hence χ(G)=minφ 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.