2024/08/11 by Hsieh, Sun-Yuan, Le, Hoang-Oanh, Le, Van Bang +1 · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2408.05865
We study a new variant of graph coloring by adding a connectivity constraint. 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 G is said to be strongly conflict-free vertex-connection k-colorable if G admits a vertex k-coloring such that any two distinct vertices of G are connected by a conflict-free shortest path. Among others, we show that deciding whether a given graph is strongly conflict-free vertex-connection 3-colorable is NP-complete even when restricted to 3-colorable graphs with diameter 3, radius 2 and domination number 3, and, assuming the Exponential Time Hypothesis (ETH), cannot be solved in 2o(n) time on such restricted input graphs with n vertices. This hardness result is quite strong when compared to the ordinary 3-COLORING problem: it is known that 3-COLORING is solvable in polynomial time in graphs with bounded domination number, and assuming ETH, cannot be solved in 2o(√(n)) time in n-vertex graphs with diameter 3 and radius 2. On the positive side, we point out that a strong conflict-free vertex-connection coloring with minimum color number of a given split graph or a co-bipartite graph can be computed in polynomial time.