The parameterized complexity of Strong Conflict-Free Vertex-Connection Colorability
Preprint
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.
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- The Complexity of Strong Conflict-Free Vertex-Connection k-colorability2025
- On Polynomial Kernelization for Stable Cutset2025
- A survey on conflict-free connection coloring of graphsDiscrete Applied Mathematics, 2024
- The Conflict-Free Vertex-Connection Number and Degree Conditions of GraphsGraphs and Combinatorics, 2022
- Optimal Data Reduction for Graph Coloring Using Low-Degree PolynomialsAlgorithmica, 2019
- Algorithms and Almost Tight Results for $3$ 3 -Colorability of Small Diameter GraphsAlgorithmica, 2014
- A Completeness Theory for Polynomial (Turing) KernelizationAlgorithmica, 2014
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics2012
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001