On properly ordered coloring of vertices in a vertex-weighted graph (Q2665834)

In this paper, the authors introduce the notion of \textit{properly order coloring} of a weighted graph, or \textit{POC}, which generalizes the notion of vertex coloring of a graph. Let \((G,w)\) be a vertex-weighted graph with vertex set \(V(G)\), edge set \(E(G)\) and a weight function \(w: V(G)\rightarrow W\), where \(W\) is a set of positive integers. A vertex coloring \(c: V(G)\rightarrow C\) on \((G,w)\), where \(C=\{1,2,\dots,\theta\}\), is a properly ordered coloring (POC) if for any edge \(uv\in E(G)\) the following conditions hold: \begin{itemize} \item if \(w(u)>w(v)\), then \(c(u)>c(v)\); \item if \(w(u)=w(v)\), then \(c(u)\ne c(v)\). \end{itemize} Then the authors define: \[ \chi_{POC}(G,w):=\min\{\theta\mid c\text{ is a POC on }(G,w)\} \] and \[ f(G):=\max\{\chi_{POC}(G,w)\mid w \text{ is a weight function on }G\}. \] Then, denoted by \(l(G)\) the number of vertices of a longest path in a graph \(G\), they prove the following: Theorem 1. Any graph \(G\) satisfies \(f(G)=l(G)\). The authors define also: \[ \chi_{POC}(G;t):=\min\{p\mid \chi_{POC}(G,w)\le p\text{ for every }w\text{ with }|W|=t\} \] and prove: Theorem 2. For a positive integer \(t\), any graph \(G\) satisfies \[ \dfrac{\chi_{POC}(G;t)-1}{\chi(G)-1}\le t. \] At last, given a digraph \(D\), let \(l'(D)\) be the number of vertices of a longest directed path in \(D\). The authors call an acyclic orientation for a vertex weighted graph \((G,w)\) \textit{good} if \(w(x)\ge w(y)\) holds for any arc \((x,y)\) in the orientation. Then, defined: \[ l'(G,w):=\min\{l'(D)\mid D\text{ is a good acyclic orientation on }(G,w) \] the authors prove the following: Theorem 3. Any weighted graph \((G,w)\) satisfies \(\chi_{POC}(G,w)=l'(G,w)\).