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 G stand for the complement of a graph G. We prove the following results: The graph C n-1 (P 2 ) is chromatically unique if and only if n = 5, 7. Almost every C n (P m ) is not chromatically unique, where n = 4 and m = 2. AMS classification: 05C15, 05C60. Copyright © 2013, Charles Babbage Research Centre.