The parameterized complexity of Strong Conflict-Free Vertex-Connection Colorability
Carl Feghali, Hoang-Oanh Le, Van Bang Lê · Discrete Applied Mathematics · 2025
This paper continues the study of a new variant of graph coloring with a connectivity constraint recently introduced by Hsieh et al. (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 vertex-connection k -colorable is fixed-parameter tractable when parameterized by the vertex cover number. But under the standard complexity-theoretic assumption NP ⊈ coNP/poly , deciding, for a given graph G , whether G is strongly conflict-free vertex-connection 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.