The Path Partition Conjecture is True and its Validity Yields Upper Bounds for Detour Chromatic Number and Star Chromatic Number

Abstract

The detour order of a graph $G$, denoted $\tau (G)$, is the order of a longest path in $G$. A partition $(A,B)$ of $V(G)$ such that $\tau (⟨A⟩)\le a$ and $\tau (⟨B⟩)\le b$ is called an $(a,b)$-partition of $G$. A graph $G$ is called $\tau$-partitionable if $G$ has an $(a,b)$-partition for every pair $(a,b)$ of positive integers such that $a+b=\tau (G)$. The well-known Path Partition Conjecture states that every graph is $\tau$-partitionable. In \cite{df07} Dunber and Frick have shown that if every 2-connected graph is $\tau$-partitionable then every graph is $\tau$-partitionable. In this paper we show that every 2-connected graph is $\tau$-partitionable. Thus, our result settles the Path Partition Conjecture affirmatively. We prove the following two theorems as the implications of the validity of the Path Partition Conjecture.\\ {\bf Theorem 1:} For every graph $G$, ${\chi }_s(G)\le \tau (G)$, where ${\chi }_s(G)$ is the star chromatic number of a graph $G$. The $n^{th}$ detour chromatic number of a graph $G$, denoted ${\chi }_n(G)$, is the minimum number of colours required for colouring the vertices of $G$ such that no path of order greater than $n$ is mono coloured. These chromatic numbers were introduced by Chartrand, Gellar and Hedetniemi\cite{cg68} as a generalization of vertex chromatic number $\chi (G)$.\\ {\bf Theorem 2:} For every graph $G$ and for every $n\ge 1$, ${\chi }_n(G)\le \lceil \frac{{\tau }_n(G)}{n}\rceil$, where ${\chi }_n(G)$ denote the $n^{th}$ detour chromatic number.\\ Theorem 2 settles the conjecture of Frick and Bullock \cite{fb01} that ${\chi }_n(G)\le \lceil \frac{\tau (G)}{n}\rceil$, for every graph $G$, for every $n\ge 1$, affirmatively.

16 pages, 1 figure