Computing Star Chromatic Number from Related Graph Invariants

Abstract

The concept of the star chromatic number of a graph was introduced by Vince \([7]\), which is a natural generalization of the chromatic number of a graph. In this paper, we will prove that if the complement of a graph \(G\) is disconnected, then its star chromatic number is equal to its chromatic number. From this, we derive a number of interesting results. Let \(G\) be a graph such that the product of its star chromatic number and its independence ratio is equal to \(1\). Then for any graph \(H\), the star chromatic number of the lexicographic product of graphs \(G\) and \(H\) is equal to the product of the star chromatic number of \(G\) and the chromatic number of \(H\). In addition, we present many classes of graphs whose star chromatic numbers are equal to their chromatic numbers.