English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The detour order of a graph $G$, denoted $\tau(G)$, is the order of a longestpath in $G$. A partition $(A, B)$ of $V(G)$ such that $\tau(\langle A \rangle)\leq a$ and $\tau(\langle B \rangle) \leq 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 every2-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 Conjectureaffirmatively. We prove the following two theorems as the implications of thevalidity of the Path Partition Conjecture.\\ {\bf Theorem 1:} For every graph$G$, $\chi_s(G) \leq \tau(G)$, where $\chi_s(G)$ is the star chromatic numberof 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 thevertices of $G$ such that no path of order greater than $n$ is mono coloured.These chromatic numbers were introduced by Chartrand, Gellar andHedetniemi\cite{cg68} as a generalization of vertex chromatic number$\chi(G)$.\\ {\bf Theorem 2:} For every graph $G$ and for every $n \geq 1$,$\chi_n(G) \leq \left\lceil \frac{\tau_n(G)}{n} \right\rceil$, where$\chi_n(G)$ denote the $n^{th}$ detour chromatic number.\\ Theorem 2 settlesthe conjecture of Frick and Bullock \cite{fb01} that $\chi_n(G) \leq\left\lceil \frac{\tau(G)}{n} \right\rceil$, for every graph $G$, for every $n\geq 1$, affirmatively.

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