Skip to main content
On Two Conjectures About the Proper Connection Number of Graphs
Discrete Mathematics
  • Fei Huang, Nankai University, China
  • Xueliang Li, Nankai University, China
  • Zhongmei Qin, Nankai University, China
  • Colton Magnant, Georgia Southern University
  • Kenta Ozeki, National Institute of Informatics, Tokyo, Japan
Document Type
Publication Date

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 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 κ(G) = 2 and minimum degree δ(G) ≥ 3, then pc(G) = 2, posed by Borozan et al. (2012). We give a family of counterexamples to disprove this conjecture. However, from a result of Thomassen 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 diam(G) = 3, then pc(G) = 2, which solves the second conjecture we want to mention, posed by Li and Magnant (2015).

Citation Information
Fei Huang, Xueliang Li, Zhongmei Qin, Colton Magnant, et al.. "On Two Conjectures About the Proper Connection Number of Graphs" Discrete Mathematics Vol. 340 Iss. 9 (2017) p. 2217 - 2222 ISSN: 0012-365X
Available at: