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

preprint2014arXivOpen access

Abstract

The detour order of a graph GG, denoted τ(G)τ(G), is the order of a longest path in GG. A partition (A,B)(A, B) of V(G)V(G) such that τ(⟨A⟩)≤aτ(\langle A \rangle) \leq a and τ(⟨B⟩)≤bτ(\langle B \rangle) \leq b is called an (a,b)(a, b)-partition of GG. A graph GG is called ττ-partitionable if GG has an (a,b)(a, b)-partition for every pair (a,b)(a, b) of positive integers such that a+b=τ(G)a + b = τ(G). 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 GG, χs(G)≤τ(G)χ_s(G) \leq τ(G), where χs(G)χ_s(G) is the star chromatic number of a graph GG. The nthn^{th} detour chromatic number of a graph GG, denoted χn(G)χ_n(G), is the minimum number of colours required for colouring the vertices of GG such that no path of order greater than nn is mono coloured. These chromatic numbers were introduced by Chartrand, Gellar and Hedetniemi\cite{cg68} as a generalization of vertex chromatic number χ(G)χ(G).\\ {\bf Theorem 2:} For every graph GG and for every n≥1n \geq 1, χn(G)≤⌈τn(G)n⌉χ_n(G) \leq \left\lceil \frac{τ_n(G)}{n} \right\rceil, where χn(G)χ_n(G) denote the nthn^{th} detour chromatic number.\\ Theorem 2 settles the conjecture of Frick and Bullock \cite{fb01} that χn(G)≤⌈τ(G)n⌉χ_n(G) \leq \left\lceil \frac{τ(G)}{n} \right\rceil, for every graph GG, for every n≥1n \geq 1, affirmatively.

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 reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.