Minimum degree and size conditions for the proper connection number of graphs.

Abstract An edge-coloured graph G is called properly connected if every two vertices are connected by a proper path. The proper connection number of a connected graph G , denoted by pc (G), is the smallest number of colours that are needed in order to make G properly connected. van Aardt et al. (2017)gave a sufficient condition for the proper connection number to be at most k in terms of the size of graphs. In this note, our main result is the following, by adding a minimum degree condition: let G be a connected graph of order n, k ≥ 3. If | E (G) | ≥ (n − m − (k + 1 − m) (δ + 1) 2) + (k + 1 − m) (δ + 1 2) + k + 2 , then pc (G) ≤ k , where m takes the value k + 1 if δ = 1 and ⌊ k δ − 1 ⌋ if δ ≥ 2. Furthermore, if k = 2 and δ = 2 , pc (G) ≤ 2, except G ∈ { G 1 , G n } (n ≥ 8), where G 1 = K 1 ∨ 3 K 2 and G n is obtained by taking a complete graph K n − 5 and K 1 ∨(2 K 2) with an arbitrary vertex of K n − 5 and a vertex with d (v) = 4 in K 1 ∨(2 K 2) being joined. If k = 2 , δ ≥ 3, we conjecture pc (G) ≤ 2, where m takes the value 1 if δ = 3 and 0 if δ ≥ 4 in the assumption. [ABSTRACT FROM AUTHOR]