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?
@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$.
