  The concept of rainbow connection number of a graph was introduced by
Chartrand et al. in 2008. Inspired by this concept, other concepts on colored
version of connectivity in graphs were introduced, such as the monochromatic
connection number by Caro and Yuster in 2011, the proper connection number by
Borozan et al. in 2012, and the conflict-free connection number by Czap et al.
in 2018, as well as some other variants of connection numbers later on.
Chakraborty et al. proved that to compute the rainbow connection number of a
graph is NP-hard. For a long time, it has been tried to fix the computational
complexity for the monochromatic connection number, the proper connection
number and the conflict-free connection number of a graph. However, it has not
been solved yet. Only the complexity results for the strong version, i.e., the
strong proper connection number and the strong conflict-free connection number,
of these connection numbers were determined to be NP-hard. In this paper, we
prove that to compute each of the monochromatic connection number, the proper
connection number and the conflict free connection number for a graph is
NP-hard. This solves a long standing problem in this field, asked in many talks
of workshops and papers.
