×

Digraphs with proper connection number two. (English) Zbl 1504.05109

Summary: A directed path in a digraph is proper if any two consecutive arcs on the path have distinct colors. An arc-colored digraph \(D\) is proper connected if for any two distinct vertices \(x\) and \(y\) of \(D\), there are both proper \((x, y)\)-directed paths and proper \((y, x)\)-directed paths in \(D\). The proper connection number \(\overrightarrow{p c}(D)\) of a digraph \(D\) is the minimum number of colors that can be used to make \(D\) proper connected. Obviously, if a digraph has a proper connection number, it must be strongly connected, and \(\overrightarrow{p c}(D) = 1\) if and only if \(D\) is complete. C. Magnant et al. [Mat. Vesn. 68, No. 1, 58–65 (2016; Zbl 1462.05159)] showed that \(\overrightarrow{p c}(D) \leq 3\) for all strong digraphs \(D\), and G. Ducoffe et al. [Discrete Appl. Math. 281, 203–215 (2020; Zbl 1440.05104)] proved that deciding whether a given digraph has proper connection number at most two is NP-complete. In this paper, we give a few classes of strong digraphs with proper connection number two, and from our proofs one can construct an optimal arc-coloring for a digraph of order \(n\) in time \(O( n^3)\).

MSC:

05C20 Directed graphs (digraphs), tournaments
05C15 Coloring of graphs and hypergraphs
05C40 Connectivity
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bang-Jensen, J.; Bellitto, T.; Yeo, A., Proper-walk connection number of graphs, J. Graph Theory, 96, 137-159 (2021)
[2] Bang-Jensen, J.; Guo, Y.; Gutin, G.; Volkmann, L., A classification of locally semicomplete digraphs, Discrete Math., 167/168, 101-114 (1997) · Zbl 0873.05072
[3] Bang-Jensen, J.; Gutin, G., Classes of Directed Graphs (2018), Springer: Springer London · Zbl 1398.05002
[4] Bang-Jensen, J.; Huang, J., Quasi-transitive digraphs, J. Graph Theory, 20, 2, 141-161 (1995) · Zbl 0832.05048
[5] Borozan, V.; Fujita, S.; Gerek, A.; Magnant, C.; Manoussakis, Y.; Montero, L.; Tuza, Zs., Proper connection of graphs, Discrete Math., 312, 17, 2550-2560 (2012) · Zbl 1246.05090
[6] Ducoffe, G.; Marinescu-Ghemeci, R.; Popa, A., On the (di)graphs with (directed) proper connection number two, Discrete Appl. Math., 281, 203-215 (2020) · Zbl 1440.05104
[7] Galeana-Sánchez, H.; Goldfeder, I. A.; Urrutia, I., On the structure of strong 3-quasi-transitive digraphs, Discrete Math., 310, 19, 2495-2498 (2010) · Zbl 1213.05112
[8] Galeana-Sánchez, H.; Hernández-Cruz, C.; Juárez-Camacho, M. A., On the existence and number of \((k + 1)\)-kings in k-quasi-transitive digraphs, Discrete Math., 313, 2582-2591 (2013) · Zbl 1281.05068
[9] Huang, F.; Li, X.; Qin, Z.; Magnant, C., Minimum degree condition for proper connection number 2, Theor. Comput. Sci., 774, 44-50 (2019) · Zbl 1428.05109
[10] Li, X.; Magnant, C., Properly colored notions of connectivity - a dynamic survey, Theory Appl. Graphs, 1, Article 2 pp. (2015)
[11] Li, X.; Magnant, C.; Qin, Z., Properly Colored Connectivity of Graphs, Springer Briefs in Math. (2018), Springer · Zbl 1475.05002
[12] Magnant, C.; Morley, P.; Porter, S.; Nowbandegani, P. S.; Wang, H., Directed proper connection of graphs, Mat. Vesn., 68, 58-65 (2016) · Zbl 1462.05159
[13] Melville, R.; Goddard, W., Coloring graphs to produce properly colored walks, Graphs Comb., 33, 1271-1281 (2017) · Zbl 1377.05097
[14] Melville, R.; Goddard, W., Properly colored trails, paths, and bridges, J. Comb. Optim., 35, 463-472 (2018) · Zbl 1386.05058
[15] Moon, J. W., On subtournaments of a tournament, Can. Math. Bull., 9, 297-301 (1966) · Zbl 0141.41204
[16] Wang, R.; Zhang, H., Hamiltonian paths in k-quasi-transitive digraphs, Discrete Math., 339, 8, 2094-2099 (2016) · Zbl 1336.05083
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.