×

On two conjectures about the proper connection number of graphs. (English) Zbl 1365.05157

Summary: A path in an edge-colored graph is called proper if no two consecutive edges of the path receive the same color. For a connected graph \(G\), the proper connection number \(\operatorname{pc}(G)\) of \(G\) is defined as the minimum number of colors needed to color its edges so that every pair of distinct vertices of \(G\) is connected by at least one proper path in \(G\). In this paper, we consider two conjectures on the proper connection number of graphs. The first conjecture states that if \(G\) is a noncomplete graph with connectivity \(\kappa(G) = 2\) and minimum degree \(\delta(G) \geq 3\), then \(\operatorname{pc}(G) = 2\), posed by V. Borozan et al. [ibid. 312, No. 17, 2550–2560 (2012; Zbl 1246.05090)]. We give a family of counterexamples to disprove this conjecture. However, from a result of C. Thomassen [in: Selected topics in graph theory. Vol. 3. London (UK) etc.: Academic Press Ltd. 97–131 (1988; Zbl 0659.05062)] it follows that 3-edge-connected noncomplete graphs have proper connection number 2. Using this result, we can prove that if \(G\) is a 2-connected noncomplete graph with \(\operatorname{diam}(G) = 3\), then \(\operatorname{pc}(G) = 2\), which solves the second conjecture we want to mention, posed by X. Li and C. Magnant [“Properly colored notions of connectivity – a dynamic survey”, Theory Appl. Graphs 0, No. 1, Article 2 (2015)].

MSC:

05C40 Connectivity
05C12 Distance in graphs
05C38 Paths and cycles
05C15 Coloring of graphs and hypergraphs

References:

[1] Andrews, E.; Laforge, E.; Lumduanhom, C.; Zhang, P., On proper-path colorings in graphs, J. Combin. Math. Combin. Comput., 97, 189-207 (2016) · Zbl 1347.05055
[2] Bondy, J. A.; Murty, U. S.R., (Graph Theory. Graph Theory, GTM, vol. 244 (2008), Springer) · Zbl 1134.05001
[3] Borozan, V.; Fujita, S.; Gerek, A.; Magnant, C.; Manoussakis, Y.; Montero, L.; Tuza, Zs., Proper connection of graphs, Discrete Math., 312, 2550-2560 (2012) · Zbl 1246.05090
[5] Chartrand, G.; Johns, G. L.; McKeon, K. A.; Zhang, P., Rainbow connection in graphs, Math. Bohem, 133, 85-98 (2008) · Zbl 1199.05106
[6] Gu, R.; Li, X.; Qin, Z., Proper connection number of random graphs, Theoret. Comput. Sci., 609, 336-343 (2016) · Zbl 1331.05194
[7] Huang, F.; Li, X.; Qin, Z.; Magnant, C., Minimum degree condition for proper connection number 2, Theoret. Comput. Sci. (2017), in press. http://dx.doi.org/10.1016/j.tcs.2016.04.042 · Zbl 1428.05109
[8] Huang, F.; Li, X.; Wang, S., Proper connection numbers of complementary graphs, Bull. Malays. Math. Sci. Soc. (2017), in press. http://dx.doi.org/10.1007/s40840-016-0381-8 · Zbl 1393.05179
[10] Li, X.; Magnant, C., Properly colored notions of connectivity - a dynamic survey, Theory Appl. Graphs, 0 (2015), Art.2. Updated in December 2016
[11] Li, X.; Shi, Y.; Sun, Y., Rainbow connections of graphs: A survey, Graphs Combin., 29, 1-38 (2013) · Zbl 1258.05058
[12] Li, X.; Sun, Y., (Rainbow Connections of Graphs, Springer Briefs in Math. (2012), Springer: Springer New York) · Zbl 1250.05066
[13] Li, X.; Wei, M.; Yue, J., Proper connection number and connected dominating sets, Theoret. Comput. Sci., 607, 480-487 (2015) · Zbl 1333.05227
[14] Thomassen, C., (Paths, circuits and subdivisions. Paths, circuits and subdivisions, Selected Topics in Graph Theory, vol. 3 (1988), Academic Press: Academic Press San Diego, CA), 97-131 · Zbl 0659.05062
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.