Abstract
The detour order of a graph , denoted , is the order of a longest path in . A partition of such that and is called an -partition of . A graph is called -partitionable if has an -partition for every pair of positive integers such that . The well-known Path Partition Conjecture states that every graph is -partitionable. In \cite{df07} Dunber and Frick have shown that if every 2-connected graph is -partitionable then every graph is -partitionable. In this paper we show that every 2-connected graph is -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 , , where is the star chromatic number of a graph . The detour chromatic number of a graph , denoted , is the minimum number of colours required for colouring the vertices of such that no path of order greater than is mono coloured. These chromatic numbers were introduced by Chartrand, Gellar and Hedetniemi\cite{cg68} as a generalization of vertex chromatic number .\\ {\bf Theorem 2:} For every graph and for every , , where denote the detour chromatic number.\\ Theorem 2 settles the conjecture of Frick and Bullock \cite{fb01} that , for every graph , for every , affirmatively.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.