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.