Almost Every Complement of a Tadpole Graph is Not Chromatically Unique

Abstract

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 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\ne 5,7$.
2. Almost every $\overline{C_n(P_m)}$ is not chromatically unique, where $n\ge 4$ and $m\ge 2$.