Almost every complement of a tadpole graph is not chromatically unique

The study of chromatically unique graphs has been drawing much attention and many results are surveyed in [4,12,13]. The notion of adjoint polynomials of graphs, which was first introduced and applied to the study of the chromaticity of the complements of the graphs by Liu [17] (see also [4]). Two invariants for adjoint equivalent graphs that have been employed successfully to determine chromatic unique graphs were introduced by Liu [17] and Dong et al. [4] respectively. In the paper, we shall utilize, among other things, these two invariants to investigate the chromaticity of the complement of the tadpole graphs $C_n(P_m)$, the graph obtained from a path $P_m$ and a cycle $C_n$ by identifying a pendant vertex of the path with a vertex of the cycle. Let $\overline{G}$ stand for the complement of a graph $G$. We prove the following results: 1) The graph $\overline{C_{n-1}(P_2)}$ is chromatically unique if and only if n ≠ 5,7. 2) Almost every $\overline{C_n(P_m)}$ is not chromatically unique, where n ≥ 4 and m ≥ 2.