{"ID":2829923,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.11725","arxiv_id":"2512.11725","title":"The parameterized complexity of Strong Conflict-Free Vertex-Connection Colorability","abstract":"This paper continues the study of a new variant of graph coloring with a connectivity constraint recently introduced by Hsieh et al. [COCOON 2024]. A path in a vertex-colored graph is called conflict-free if there is a color that appears exactly once on its vertices. A connected graph is said to be strongly conflict-free vertex-connection $k$-colorable if it admits a (proper) vertex $k$-coloring such that any two distinct vertices are connected by a conflict-free shortest path. Among others, we show that deciding, for a given graph $G$ and an integer $k$, whether $G$ is strongly conflict-free $k$-colorable is fixed-parameter tractable when parameterized by the vertex cover number. But under the standard complexity-theoretic assumption NP $\\not\\subseteq$ coNP/poly, deciding, for a given graph $G$, whether $G$ is strongly conflict-free $3$-colorable does not admit a polynomial kernel, even for bipartite graphs. This kernel lower bound is in stark contrast to the ordinal $k$-Coloring problem which is known to admit a polynomial kernel when parameterized by the vertex cover number.","short_abstract":"This paper continues the study of a new variant of graph coloring with a connectivity constraint recently introduced by Hsieh et al. [COCOON 2024]. A path in a vertex-colored graph is called conflict-free if there is a color that appears exactly once on its vertices. A connected graph is said to be strongly conflict-fr...","url_abs":"https://arxiv.org/abs/2512.11725","url_pdf":"https://arxiv.org/pdf/2512.11725v1","authors":"[\"Carl Feghali\",\"Hoang-Oanh Le\",\"Van Bang Le\"]","published":"2025-12-12T17:05:37Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\",\"cs.DM\",\"math.CO\"]","methods":"[\"LoRA\"]","has_code":false}