A graph G of order n is called k-step Hamiltonian for k ≥ 1 if we can label the vertices of G as v1, v2,..., vn such that d(vn, v1) = d(vi, vi+1) = k for i = 1, 2,..., n-1. The (vertex) chromatic number of a graph G is the minimum number of colors needed to color the vertices of G so that no pair of adjacent vertices receive the same color. The clique number of G is the maximum cardinality of a set of pairwise adjacent vertices in G. In this paper, we study the chromatic number and the clique number in k-step Hamiltonian graphs for k ≥ 2. We present upper bounds for the chromatic number in k-step Hamiltonian graphs and give characterizations of graphs achieving the equality of the bounds. We also present an upper bound for the clique number in k-step Hamiltonian graphs and characterize graphs achieving equality of the bound. [ABSTRACT FROM AUTHOR]