Volume 35 • Number 1 • 2012   • Chromaticity of Complete 6-Partite Graphs with Certain Star or Matching Deleted H. Roslan, A. Sh. Ameen, Y. H. Peng and H. X. Zhao 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 6-partite graphs with $6n$ vertices according to the number of 7-independent partitions of $G$. Using these results, we investigate the chromaticity of $G$ with certain star or matching deleted. As a by-product, many new families of chromatically unique complete 6-partite graphs with certain star or matching deleted are obtained. 2010 Mathematics Subject Classification: 05C15. Full text: PDF