Let G be a finite simple graph. Consider the independent number $\alpha$, the chromatic number $\chi$ and the path cover number (also called the path partition number) $\rho$.
Then we have $\alpha\chi \ge n$ and $\alpha \ge \rho$.


Is there any relationships between the path cover number $\rho$ and the chromatic number $\chi$ ? For example, is the inequality $\rho\chi\ge n$ true?



Is there any relationships between path cover number and chromatic number?
@vidyarthi: The answer to your question is too long for a comment.


Let $G$ be a simple graph and let $\rho$ be the smallest integer such that there exists a system of pairwise disjoint paths $P\_1,\ldots,P\_\rho$ containing all vertices of $G$. Then we assume $\rho(G)=\rho$. By the way, sometimes $\rho(G)=-1$ is assumed if $G$ is hamiltonian and $\rho(G)=0$ if $G$ is hamiltonian but not hamiltonian-connected.


It is argued that the following statement is true.



> 
> For any graph $G$ the following inequality holds:
> $$ \chi(G)+\rho(G)\leq n+1, 
> $$ where
> $n$ is the order of graph $G$ and $\chi(G)$ is the chromatic number of
> $G$.
> 
> 
> 


*Proof.*
Choose in each path $P\_i$ one of its ends. Denote this vertex by $v\_i$.
The set $X=\{v\_1,\ldots,v\_\rho\}$ is an independent set in the graph $G$. In fact, if $v\_iv\_j$ is an edge of $G$, then we can replace paths $P\_i$ and $P\_j$ by one path $P=P\_i\cup P\_j$. Contradiction.


Now let us color all vertices of $X$ with the same color.


Let us paint the remaining $n-\rho$ vertices of graph $G$ in $n-\rho$ other different colors.
Thus we used exactly $n-\rho+1$ colors for the correct coloring of graph $G$. Hence $\chi\leq n-\rho+1$.


