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.