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\).
05C15 Coloring of graphs and hypergraphs
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)