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 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.  https://doi.org/10.1007/s00373-002-0492-x
[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.  https://doi.org/10.1016/j.disc.2011.12.014
[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.  https://doi.org/10.1016/j.akcej.2017.11.007
[12] B. Randerath and I. Schiermeyer, Vertex colouring and forbidden subgraphs- A survey, Graphs Combin. 20 (2004), no. 1, 1–40.  https://doi.org/10.1007/s00373-003-0540-1
[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.  https://doi.org/10.1016/j.dam.2011.08.005
[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
Volume 9, Issue 1
March 2024
Pages 37-49

Files

Share

How to cite

Statistics