On the (di)graphs with (directed) proper connection number two

• DOI: 10.1016/j.dam.2019.06.024
• Publication Date: 2019-07-10T12:20:25Z
• Authors: Guillaume Ducoffe; Ruxandra Marinesc...; Alexandru Popa
• Keywords: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]; [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]; bipartite; [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]; 0102 computer and information sciences; [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]; proper connection; directed graphs; 01 natural sciences; [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]; [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]; [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]; [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC]; even dicycles; digraphs; NP-complete

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 Mag-nant 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.