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

Document Type : Original paper

Authors

1 School of Mathematical Sciences , Universiti Sains Malaysia, 11800 Penang, Malaysia

2 Department of Mathematics, Shahed University, Tehran, Iran

3 School of Mathematical Sciences, Universiti Sains Malaysia, 11800 Penang, Malaysia

4 Faculty of Ocean Engineering Technology and Informatics, Universiti Malaysia Terengganu, 21030 Kuala Nerus, Terengganu Malaysia

Abstract

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.

Keywords

Main Subjects

References

[1] N. A. Abd Aziz, N. Jafari Rad, H. Kamarulhaili, and R. Hasni, A note on k−step Hamiltonian graphs, Malaysian J. Math. Sci. 13 (2019), no. 1, 87–93.
[2] N.A. Abd Aziz, N. Jafari Rad, H. Kamarulhaili, and R. Hasni, Bounds for the independence number in k-step Hamiltonian graphs, Comput. Sci. J. Moldova 26 (2018), no. 1, 15–28.
[3] G. Chartrand, L. Lesniak, and P. Zhang, Graphs & Digraphs, 5th ed., CRC Press, Boca Raton, Florida, USA, 2011.
[4] R.J. Gould, Advances on the Hamiltonian problem: A survey, Graphs Combin. 19 (2003), no. 1, 7–52.
[5] Y.S. Ho, S.M. Lee, and B. Lo, On 2−steps Hamiltonian cubic graphs, J. Combin. Math. Combin. Comput. 98 (2016), 185–199.
[6] A.V. Kostochka, L. Rabern, and M. Stiebitz, Graphs with chromatic number close to maximum degree, Discrete Math. 312 (2012), no. 6, 1273–1281.
[7] G.C. Lau, Y.S. Ho, S.M. Lee, and K. Schaffer, On 3−step Hamiltonian trees, J. Graph Labeling 1 (2015), 41–53.
[8] G.C. Lau, S.M. Lee, K. Schaffer, and S.M. Tong, On k−step Hamiltonian bipartite and tripartite graphs, Malaya J. Mat. 2 (2014), no. 3, 180–187.
[9] G.C. Lau, S.M. Lee, K. Schaffer, S.M. Tong, and S. Lui, On k−step hamiltonian graphs, J. Combin. Math. Combin. Comput. 90 (2014), 145–158.
[10] S.M. Lee and H.H. Su, On 2−steps Hamiltonian subdivision graphs of cycles with a chord, J. Combin. Math. Combin. Comput. 98 (2016), 109–123.
[11] P.K. Niranjan and R.K. Srinivasa, The k−distance chromatic number of trees and cycles, AKCE Int. J. Graphs Comb. 16 (2019), no. 2, 230–235.
[12] B. Randerath and I. Schiermeyer, Vertex colouring and forbidden subgraphs- A survey, Graphs Combin. 20 (2004), no. 1, 1–40.
[13] M. Soto, A. Rossi, and M. Sevaux, Three new upper bounds on the chromatic number, Discrete Appl. Math. 159 (2011), no. 18, 2281–2289.
[14] L. Stacho, New upper bounds for the chromatic number of a graph, J. Graph Theory 36 (2001), no. 2, 117–120.
[15] D.B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle River, New Jersey, USA, 2001.
 
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 03 November 2022

Files

Share

How to cite

Statistics