On path-chromatically unique graphs Original Research Article

The least number of colors needed to color the vertices of a graph G such that the vertices in each color class induces a linear forest is called the path-chromatic number of G, denoted by χ∞(G). If all such colorings of the vertices of G induce the same partitioning of the vertices of G, we say that G is path-chromatically unique. We prove here that there exist infinitely many path-chromatically unique graphs with path-chromatic number t, for each t ⩾ 1. We also show that path-chromatically unique graphs of order n and path-chromatic number t ⩾ 2 exist only for n ⩾ 4t − 1.