Solution to a conjecture on the proper connection number of graphs

Abstract

A path in an edge-colored graph is called a proper path if no two adjacent 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\). Recently, Li and Magnant in [Theory Appl. Graphs 0(1)(2015), Art.2] posed the following conjecture: If \(G\) is a connected noncomplete graph of order \(n \geq 5\) and minimum degree \(\delta(G) \geq n/4\), then \(pc(G)=2\). In this paper, we show that this conjecture is true except for two small graphs on 7 and 8 vertices, respectively. As a byproduct we obtain that if \(G\) is a connected bipartite graph of order \(n\geq 4\) with \(\delta(G)\geq \frac{n+6}{8}\), then \(pc(G)=2\).