A new method for proving chromatic uniqueness of graphs (Q1363698)

A graph \(G\) is chromatically unique if each graph with the same chromatic polynomial as \(G\) is isomorphic to \(G\). The authors present some methods for proving chromatic uniqueness of certain graphs \(G\) by using algebraic properties of their adjoint polynomials \(\sum^p_{i=1}a_ix^i\) in which \(p\) is the order of \(G\) and \(a_i\) is the number of partitions of \(V(G)\) into \(i\) nonempty cliques for \(i=1,\dots,p\). Besides some simpler proofs of former results about adjoint polynomials and chromatic uniqueness, the authors also present a new family of chromatically unique graphs: For \(n\geq 6\), \(F_n\) denotes a graph consisting of two disjoint triangles connected by a path with \(n-4\) vertices. It is proved that the complement \(\overline{F_n}\) of \(F_n\) is chromatically unique if \(F_n\) is irreducible, i.e. the adjoint polynomial \(\sum^p_{i=1} a_ix^i\) of \(F_n\) divided by \(x^\alpha\) is irreducible where \(\alpha\) is the smallest index \(i\) with \(a_i\neq 0\). However, the authors verify irreducibility only for \(F_6\) and \(F_{10}\). They leave it open whether \(F_n\) is irreducible and \(\overline{F_n}\) is chromatically unique for infinitely many numbers \(n\geq 6\).