Chromaticity of Complete Tripartite Graphs With Certain Star or Matching Deleted

Abstract

Let \(P(G,\lambda)\) be the chromatic polynomial of a graph \(G\). Two graphs \(G\) and \(H\) are said to be chromatically equivalent, denoted \(G \sim H\), if \(P(G,\lambda) = P(H,\lambda)\). We write \([G] = \{H | H \sim G\}\). If \([G] = \{G\}\), then \(G\) is said to be chromatically unique. In this paper, we first characterize certain complete tripartite graphs \(G\) according to the number of \(4\)-independent partitions of \(G\). Using these results, we investigate the chromaticity of \(G\) with certain star or matching deleted. As a by-product, we obtain new families of chromatically unique complete tripartite graphs with certain star or matching deleted.