# zbMATH — the first resource for mathematics

Almost every complement of a tadpole graph is not chromatically unique. (English) Zbl 1289.05176
Summary: The study of chromatically unique graphs has been drawing much attention and many results are surveyed in [F. M. Dong et al., Chromatic polynomials and chromaticity of graphs. Singapore: World Scientific Publishing (2005; Zbl 1070.05038); K. M. Koh and K. L. Teo, Graphs Comb. 6, No. 3, 259–285 (1990; Zbl 0727.05023); Discrete Math. 172, No. 1–3, 59–78 (1997; Zbl 0879.05031)]. 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 R. Y. Liu [Discrete Math. 172, No. 1–3, 85–92 (1997; Zbl 0878.05030)] (see also [Dong et al., loc. cit.]). Two invariants for adjoint equivalent graphs that have been employed successfully to determine chromatic unique graphs were introduced by Liu [loc. cit.] and by Dong et al. [loc. cit.], respectively. In this 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 $$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\neq 5,7$$.
2. Almost every $$\overline {C_n(P_m)}$$ is not chromatically unique, where $$n\geq 4$$ and $$m\geq 2$$.
##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)