zbMATH — the first resource for mathematics

Path chromatic numbers of graphs. (English) Zbl 0688.05024
Summary: 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 i and let $$<V_ i>$$ be the subgraph of G induced by $$V_ i$$. The k-path chromatic number of G, denoted by $$\chi (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\leq i\leq c$$. We obtain upper bounds for $$\chi (G;P_ k)$$ and $$\chi (G;P_{\infty})$$ for regular, planar, and outerplanar graphs.

MSC:
 05C15 Coloring of graphs and hypergraphs 05C35 Extremal problems in graph theory 05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: