2025/12/12 by Feghali, Carl, Le, Hoang-Oanh, Le, Van Bang
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2512.11725
openalex publication_date 2025/12/12 · openalex created_date 2025/12/16 · openalex updated_date 2026/07/28
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⊆ 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.