Azarbaijan Shahid Madani University Communications in Combinatorics and Optimization 2538-2128 9 1 2024 03 01 On chromatic number and clique number in k-step Hamiltonian graphs 37 49 14462 10.22049/cco.2022.27970.1407 EN Noor A'lawiah Abd Aziz School of Mathematical Sciences , Universiti Sains Malaysia, 11800 Penang, Malaysia Nader Jafari Rad Department of Mathematics, Shahed University, Tehran, Iran Hailiza Kamarulhaili School of Mathematical Sciences , Universiti Sains Malaysia, 11800 Penang, Malaysia Roslan Hasni Faculty of Ocean Engineering Technology and Informatics, Universiti Malaysia Terengganu, 21030 Kuala Nerus, Terengganu Malaysia Journal Article 2022 08 22 A graph $G$ of order $n$ is called $k-$step Hamiltonian for $k\geq 1$ if we can label the vertices of $G$ as $v_1,v_2,\ldots,v_n$ such that $d(v_n,v_1)=d(v_i,v_{i+1})=k$ for $i=1,2,\ldots,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\geq 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. https://comb-opt.azaruniv.ac.ir/article_14462_ad2836eddac7d6724175272ced1d03ce.pdf