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≥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.

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