×

On the (di)graphs with (directed) proper connection number two. (English) Zbl 1440.05104

Summary: 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 C. Magnant et al. [Mat. Vesn. 68, No. 1, 58–65 (2016; Zbl 1462.05159)] 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.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C15 Coloring of graphs and hypergraphs
05C40 Connectivity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Citations:

Zbl 1462.05159

Software:

Algorithm 447
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Ananth, P.; Nasre, M., New Hardness Results in Rainbow ConnectivityTechnical Report (2011), arXiv:1104.2074v1, arXiv
[2] Andrews, E.; Lumduanhom, C.; Laforge, E.; Zhang, P., On proper-path colorings in graphs, J. Combin. Math. Combin. Comput., 97, 189-207 (2016) · Zbl 1347.05055
[3] Bang-Jensen, J.; Gutin, G., Alternating cycles and paths in edge-coloured multigraphs: a survey, Discrete Math., 165, 39-60 (1997) · Zbl 0876.05057
[4] Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications (2008), Springer Science & Business Media
[5] Bodlaender, H., (Treewidth: Characterizations, Applications, and Computations. Treewidth: Characterizations, Applications, and Computations, WG’06. Treewidth: Characterizations, Applications, and Computations. Treewidth: Characterizations, Applications, and Computations, WG’06, LNCS, vol. 4271 (2016), Springer), 1-14 · Zbl 1167.68404
[6] Bondy, J. A.; Murty, U. S.R., (Graph Theory. Graph Theory, Grad. Texts in Math. (2008)) · Zbl 1134.05001
[7] Borozan, V.; Fujita, S.; Gerek, A.; Magnant, C.; Manoussakis, Y.; Montero, L.; Tuza, Z., Proper connection of graphs, Discrete Math., 312, 17, 2550-2560 (2012) · Zbl 1246.05090
[8] Brause, C.; Doan, T.; Schiermeyer, I., Minimum degree conditions for the proper connection number of graphs, Graphs Combin., 33, 4, 833-843 (2017) · Zbl 1371.05153
[9] Chakraborty, S.; Fischer, E.; Matsliah, A.; Yuster, R., Hardness and algorithms for rainbow connection, J. Comb. Optim., 21, 3, 330-347 (2011) · Zbl 1319.05049
[10] Chang, H.; Huang, Z.; Li, X., Degree Sum Conditions for Graphs to Have Proper Connection Number 2Technical Report (2016), arXiv:1611.09500, arXiv
[11] Chartrand, G.; Johns, G. L.; McKeon, K. A.; Zhang, P., Rainbow connection in graphs, Math. Bohem., 133, 1, 85-98 (2008) · Zbl 1199.05106
[12] Chartrand, G.; Zhang, P., Radio colorings of graphs - a survey, Int. J. Appl. Comput. Math., 2, 3, 237-252 (2007)
[13] Chizmar, E.; Magnant, C.; Salehi Nowbandegani, P., Note on vertex and total proper connection numbers, AKCE Int. J. Graphs Comb., 13, 1, 103-106 (2016) · Zbl 1348.05112
[14] Chou, W.; Manoussakis, Y.; Megalakaki, O.; Spyratos, M.; Tuza, Z., Paths through fixed vertices in edge-colored graphs, Math. Sci. Hum., 127, 49-58 (1994) · Zbl 0826.68064
[15] Courcelle, B., The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inform. and comput., 85, 1, 12-75 (1990) · Zbl 0722.03008
[16] Dorninger, D., On permutations of chromosomes, (Contributions to General Algebra, Vol. 5 (1987)), 95-103 · Zbl 0643.92012
[17] Dorninger, D., Hamiltonian circuits determining the order of chromosomes, Discrete Appl. Math., 50, 2, 159-168 (1994) · Zbl 0823.92010
[18] Dorninger, D.; Timischl, W., Geometrical constraints on Bennett’s predictions of chromosome order, Heredity, 58, 1, 321-325 (1987)
[19] G. Ducoffe, R. Marinescu-Ghemeci, A. Popa, On the (di)graphs with (directed) proper connection number two, in: IX Latin and American Algorithms, Graphs and Optimization Symposium, Vol. 62, LAGOS, 2017, pp. 237-242. · Zbl 1383.05130
[20] Gerek, A.; Fujita, S.; Magnant, C., Proper connection with many colors, J. Comb., 3, 4, 683-693 (2012) · Zbl 1270.05040
[21] Grötschel, M., On minimal strong blocks, J. Graph Theory, 3, 3, 213-219 (1979) · Zbl 0414.05030
[22] Gu, R.; Li, X.; Qin, Z., Proper connection number of random graphs, Theoret. Comput. Sci., 609, 336-343 (2016) · Zbl 1331.05194
[23] Hale, W. K., Frequency assignment: theory and applications, Proc. IEEE, 68, 1497-1514 (1980)
[24] Han, X.; Kelsen, P.; Ramachandran, V.; Tarjan, R., Computing minimal spanning subgraphs in linear time, SIAM J. Comput., 24, 6, 1332-1358 (1995) · Zbl 0841.05084
[25] Hopcroft, J.; Tarjan, R., Algorithm 447: efficient algorithms for graph manipulation, Commun. ACM, 16, 6, 372-378 (1973)
[26] Huang, F.; Li, X.; Qin, Z.; Magnant, C., Minimum degree condition for proper connection number 2, Theoret. Comput. Sci. (2016)
[27] Huang, F.; Li, X.; Wang, S., Proper Connection Number and 2-Proper Connection Number of a GraphTechnical Report (2015), arXiv:1507.01426, arXiv
[28] Huang, F.; Li, X.; Wang, S., Proper connection numbers of complementary graphs, Bull. Malays. Math. Sci. Soc., 1-11 (2016)
[29] Jiang, H.; Li, X.; Zhang, Y., Total Proper Connection of GraphsTechnical Report (2015), arXiv:1512.00726, arXiv
[30] Jiang, H.; Li, X.; Zhang, Y.; Zhao, Y., On (strong) proper vertex-connection of graphs, Bull. Malays. Math. Sci. Soc., 41, 415-425 (2018) · Zbl 1387.05089
[31] Li, X.; Magnant, C., Properly colored notions of connectivity-a dynamic survey, Theory Appl. Graphs, 1, 2 (2015)
[32] Li, X.; Wei, M.; Yue, J., Proper connection number and connected dominating sets, Theoret. Comput. Sci., 607, 480-487 (2015) · Zbl 1333.05227
[33] Lumduanhom, C.; Laforge, E.; Zhang, P., Characterizations of graphs having large proper connection numbers, Discuss. Math. Graph Theory, 36, 2, 439-453 (2016) · Zbl 1338.05088
[34] Magnant, C.; Morley, P. R.; Porter, S.; Nowbandegani, P. S.; Wang, H., Directed proper connection of graphs, Mat. Vesnik, 68, 1, 58-65 (2016) · Zbl 1462.05159
[35] McCuaig, W., Even dicycles, J. Graph Theory, 35, 1, 46-68 (2015) · Zbl 0958.05070
[36] McCuaig, W.; Robertson, N.; Seymour, P.; Thomas, R., (Permanents, Pfaffian Orientations, and Even Directed Circuits. Permanents, Pfaffian Orientations, and Even Directed Circuits, STOC’97 (1997)), 402-405 · Zbl 0963.68153
[37] Melville, R.; Goddard, W., Coloring graphs to produce properly colored walks, Graphs Combin., 33, 5, 1271-1281 (2017) · Zbl 1377.05097
[38] Schaefer, T., The complexity of satisfiability problems, (STOC (1978), ACM), 216-226 · Zbl 1282.68143
[39] Schmidt, J. M., A simple test on 2-vertex- and 2-edge-connectivity, Inform. Process. Lett., 113, 7, 241-244 (2013) · Zbl 1259.05173
[40] Tarjan, R. E., A note on finding the bridges of a graph, Inform. Process. Lett., 2, 6, 160-161 (1974) · Zbl 0282.68018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.