Chromaticity of Turan Graphs with Certain Matching or Star Deleted

Abstract

Let $P(G,\lambda )$ be the chromatic polynomial of a graph $G$. A graph $G$ is chromatically unique if for any graph $H$, $P(H,\lambda )=P(G,\lambda )$ implies H is isomorphic to $G$. In this paper, we study the chromaticity of Turén graphs with deleted edges that induce a matching or a star. As a by-product, we obtain new families of chromatically unique graphs.