Abstract :

A coloring of a graph $G$ is an assignment of colors to the vertices of $G$ such that no two adjacent vertices receive the same color. The set of vertices with the same color is called a color class. A star coloring of a graph $G$ is a coloring of $G$ such that the union of any two color classes induce a star forest. That is, a coloring of $G$ such that no path on four vertices is bi-colored. The star chromatic number of $G$ is the minimum number of colors required to star color $G$, and is denoted by $chi_ s(G)$. The computation of $chi_ s(G)$ is NP-hard in general. In this talk, we present some general bounds for $chi_ s$, and then use it to derive bounds for $chi_ s$ in certain graph classes.