On chromatic number and clique number in k-step Hamiltonian graphs

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.