Path chromatic numbers of graphs

Abstract

Abstract Let the finite, simple, undirected graph G = ( V ( G ), E ( G )) be vertex‐colored. Denote the distinct colors by 1,2,…, c. Let V i be the set of all vertices colored j and let < V i be the subgraph of G induced by V i . The k ‐path chromatic number of G , denoted by χ( G ; P k ), is the least number c of distinct colors with which V ( G ) can be colored such that each connected component of V i is a path of order at most k , 1 ⩽ i ⩽ c. We obtain upper bounds for χ( G ; P k ) and χ( G ; P ∞ ) for regular, planar, and outerplanar graphs.