TY - JOUR
T1 - On the (di)graphs with (directed) proper connection number two
AU - Ducoffe, Guillaume
AU - Marinescu-Ghemeci, Ruxandra
AU - Popa, Alexandru
N1 - Funding Information:
We wish to thank the referees for their careful reading of the first version of this manuscript, and their useful comments. This work was partly supported by the Institutional research programme PN 1819 “Advanced IT resources to support digital transformation processes in the economy and society - RESINFO-TD” (2018), project PN 1819-01-01 “Modeling, simulation, optimization of complex systems and decision support in new areas of IT&C research”, funded by the Ministry of Research and Innovation, Romania .
PY - 2020/7/15
Y1 - 2020/7/15
N2 - The (directed) proper connection number of a given (di)graph G is the least number of colors needed to edge-color G such that there exists a properly colored (di)path between every two vertices in G. There also exist vertex-coloring versions of the proper connection number in (di)graphs. We initiate the study of the complexity of computing the proper connection number and (two variants of) the proper vertex connection number, in undirected and directed graphs, respectively. First we disprove some conjectures of Magnant et al. (2016) on characterizing strong digraphs with directed proper connection number at most two. In particular, we prove that deciding whether a given digraph has directed proper connection number at most two is NP-complete. Furthermore, we show that there are infinitely many such digraphs without an even-length dicycle. To the best of our knowledge, the proper vertex connection number of digraphs has not been studied before. We initiate the study of proper vertex connectivity in digraphs and we prove similar results as for the arc version. Finally, on a more positive side we present polynomial-time recognition algorithms for bounded-treewidth graphs and bipartite graphs with proper connection number at most two.
AB - The (directed) proper connection number of a given (di)graph G is the least number of colors needed to edge-color G such that there exists a properly colored (di)path between every two vertices in G. There also exist vertex-coloring versions of the proper connection number in (di)graphs. We initiate the study of the complexity of computing the proper connection number and (two variants of) the proper vertex connection number, in undirected and directed graphs, respectively. First we disprove some conjectures of Magnant et al. (2016) on characterizing strong digraphs with directed proper connection number at most two. In particular, we prove that deciding whether a given digraph has directed proper connection number at most two is NP-complete. Furthermore, we show that there are infinitely many such digraphs without an even-length dicycle. To the best of our knowledge, the proper vertex connection number of digraphs has not been studied before. We initiate the study of proper vertex connectivity in digraphs and we prove similar results as for the arc version. Finally, on a more positive side we present polynomial-time recognition algorithms for bounded-treewidth graphs and bipartite graphs with proper connection number at most two.
KW - Directed graphs
KW - Even dicycles
KW - NP-complete
KW - Proper connection
UR - http://www.scopus.com/inward/record.url?scp=85068509645&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85068509645&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2019.06.024
DO - 10.1016/j.dam.2019.06.024
M3 - Article
AN - SCOPUS:85068509645
VL - 281
SP - 203
EP - 215
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
SN - 0166-218X
ER -