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