  We introduce the notion of a properly ordered coloring (POC) of a weighted
graph, that generalizes the notion of vertex coloring of a graph. Under a POC,
if $xy$ is an edge, then the larger weighted vertex receives a larger color; in
the case of equal weights of $x$ and $y$, their colors must be different. In
this paper, we shall initiate the study of this special coloring in graphs. For
a graph $G$, we introduce the function $f(G)$ which gives the maximum number of
colors required by a POC over all weightings of $G$. We show that
$f(G)=\ell(G)$, where $\ell(G)$ is the number of vertices of a longest path in
$G$.
  Another function we introduce is $\chi_{POC}(G;t)$ giving the minimum number
of colors required over all weightings of $G$ using $t$ distinct weights. We
show that the ratio of $\chi_{POC}(G;t)-1$ to $\chi(G)-1$ can be bounded by $t$
for any graph $G$; in fact, the result is shown by determining
$\chi_{POC}(G;t)$ when $G$ is a complete multipartite graph.
  We also determine the minimum number of colors to give a POC on a
vertex-weighted graph in terms of the number of vertices of a longest directed
path in an orientation of the underlying graph. This extends the so called
Gallai-Hasse-Roy-Vitaver theorem, a classical result concerning the
relationship between the chromatic number of a graph $G$ and the number of
vertices of a longest directed path in an orientation of $G$.
