Chromatic number and Hamiltonicity of graphs

Rao Li 1
1Dept. of Mathematical Sciences University of South Carolina Aiken Aiken, SC 29801

Abstract

Let \( G \) be a \( k \)-connected (\( k > 2 \)) graph of order \( n \). If \( \chi(G) > n-k \), then \( G \) is Hamiltonian or \( K_k \vee (K_{n-2k}) \) with \( n > 2k+1 \), where \( \chi(G) \) is the chromatic number of the graph \( G \).

Keywords: Hamiltonicity, chromatic number