Almost every complement of a tadpole graph is not chromatically unique

作者：Wang J F^*; Huang Q X; Teo K L; Belardo F; Liu R Y; Ye C F

来源：Ars Combinatoria, 2013, 108: 33-49.

• chromatic polynomials
• chromatically unique
• adjoint polynomials
• adjointly unique
• characters

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 (G) over bar stand for the complement of a graph G. We prove the following results: %26lt;br%26gt;1. The graph %26lt;(Cn-1(P-2))over bar%26gt; is chromatically unique if and only if n not equal 5, 7. %26lt;br%26gt;2. Almost every %26lt;(C-n(P-m))over bar%26gt; is not chromatically unique, where n %26gt;= 4 and m %26gt;= 2.

• 出版日期2013-1
• 单位新疆大学; 青海师范大学