Menu
A linear layout, or simply a layout, of an undirected graph \( G = (V, E) \) with \( n = |V| \) vertices is a bijective function \( \phi: V \to \{1, 2, \dots, n\} \). A \( k \)-coloring of a graph \( G = (V, E) \) is a mapping \( \kappa: V \to \{c_1, c_2, \dots, c_k\} \) such that no two adjacent vertices have the same color. A graph with a \( k \)-coloring is called a \( k \)-colored graph.
A colored layout of a \( k \)-colored graph \( (G, \kappa) \) is a layout \( \phi \) of \( G \) such that for any \( u, x, v \in V \), if \( (u, v) \in E \) and \( \phi(u) < \phi(x) < \phi(v) \), then \( \kappa(u) \neq \kappa(x) \). Given a \( k \)-colored graph \( (G, \kappa) \), the problem of deciding whether there is a colored layout \( \phi \) of \( (G, \kappa) \) is NP-complete. In this paper, we introduce the concept of chromatic layout of \( G \) and determine the chromatic layout number for paths and cycles.