Back to Search
Start Over
Proper rainbow connection number of graphs
- Publication Year :
- 2019
-
Abstract
- A path in an edge-coloured graph is called \emph{rainbow path} if its edges receive pairwise distinct colours. An edge-coloured graph is said to be \emph{rainbow connected} if any two distinct vertices of the graph are connected by a rainbow path. The minimum $k$ for which there exists such an edge-colouring is the rainbow connection number $rc(G)$ of $G.$ Recently, Bau et al. \cite{BJJKM2018} introduced this concept with the additional requirement that the edge-colouring must be proper. %An proper edge-coloured graph is said to be \emph{properly rainbow connected} if any two distinct vertices of the graph are connected by a rainbow path. The \emph{proper rainbow connection number} of $G$, denoted by $prc(G)$, is the minimum number of colours needed in order to make it properly rainbow connected. In this paper we first prove an improved upper bound $prc(G) \leq n$ for every connected graph $G$ of order $n \geq 3.$ Next we show that the difference $prc(G) - rc(G)$ can be arbitrarily large. Finally, we present several sufficient conditions for graph classes satisfying $prc(G) = \chi'(G).$
- Subjects :
- Mathematics - Combinatorics
05C15, 05C40, 05C07
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1911.01118
- Document Type :
- Working Paper