2016/02/23 by Fei Huang, Xueliang Li, Huang, Fei +7
Computer Science · Mathematics · #05C15 #05C40 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Interconnection Networks and Systems #math.CO #msc:05C15 #msc:05C40
paper · pdf · doi:10.48550/arxiv.1602.07163
10 pages. arXiv admin note: text overlap with arXiv:1601.04162
openalex publication_date 2016/02/23 · arxiv created 2016/03/28 · arxiv updated 2016/03/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 are 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.~in [Discrete Math. 312(2012), 2550-2560]. 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 in [Theory & Appl. Graphs 0(1)(2015), Art.2].