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.

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