Upper bounds of proper connection number of graphs (Q2410035)

The authors study the proper connection number of graphs, a parameter similar to the rainbow connection number. Given a (not necessarily proper) edge coloring of a graph \(G\), a path in \(G\) is said to be proper if no two adjacent edges in the path receive the same color. An edge-colored graph is proper connected if every pair of vertices is joined by a proper path. (Thus, a proper edge-coloring of a connected graph is automatically proper connected, but it may be possible to use fewer colors in an edge-coloring that is merely proper connected.) The proper connection number of \(G\), written \(\operatorname{pc}(G)\), is the smallest number of colors that can be used in a proper connected coloring of \(G\). For nontrivial connected graphs \(G\), the authors obtain the upper bound \(\operatorname{pc}(G) \leq \max\{3, \Delta(G^\ast)\}\), where \(G^\ast\) is the bridge-block tree of \(G\). The authors also obtain the following Erdős-Gallai-type result. Let \(f(n,k)\) be the smallest integer such that \(|E(G)| \geq f(n,k)\) implies \(\operatorname{pc}(G) \leq k\) for every connected \(n\)-vertex graph \(G\). (Note that, for example, a complete graph has \(\operatorname{pc}(G) = 1\), so this question makes sense.) The authors prove that \(f(n,k) \geq {n-k-1 \choose 2} + k + 2\) for any \(k \geq 2\), and that equality holds if \(k \geq 3\) or if \(k=2\) and \(n \geq 14\).