The complexity of strong conflict-free vertex-connection $k$-colorability
<|reference_start|>The complexity of strong conflict-free vertex-connection $k$-colorability: 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 $2^{o(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 $2^{o(\sqrt{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.<|reference_end|>
@article{hsieh2024the,
    title={The complexity of strong conflict-free vertex-connection
  $k$-colorability},
    author={Sun-Yuan Hsieh, Hoang-Oanh Le, Van Bang Le, Sheng-Lung Peng},
    journal={arXiv preprint arXiv:2408.05865},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.05865},
    primaryClass={cs.CC cs.DM cs.DS}
}