1 results
NOTE ON MINIMUM DEGREE AND PROPER CONNECTION NUMBER
- Part of
-
- Journal:
- Bulletin of the Australian Mathematical Society / Volume 103 / Issue 2 / April 2021
- Published online by Cambridge University Press:
- 03 July 2020, pp. 177-181
- Print publication:
- April 2021
-
- Article
- Export citation
-
An edge-coloured graph
$G$ is called properly connected if any two vertices are connected by a properly coloured path. The proper connection number, 
$pc(G)$, of a graph 
$G$, is the smallest number of colours that are needed to colour 
$G$ such that it is properly connected. Let 
$\unicode[STIX]{x1D6FF}(n)$ denote the minimum value such that 
$pc(G)=2$ for any 2-connected incomplete graph 
$G$ of order 
$n$ with minimum degree at least 
$\unicode[STIX]{x1D6FF}(n)$. Brause et al. [‘Minimum degree conditions for the proper connection number of graphs’, Graphs Combin.33 (2017), 833–843] showed that 
$\unicode[STIX]{x1D6FF}(n)>n/42$. In this note, we show that 
$\unicode[STIX]{x1D6FF}(n)>n/36$.
