A new method for proving chromatic uniqueness of graphs (Q1363698)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A new method for proving chromatic uniqueness of graphs |
scientific article |
Statements
A new method for proving chromatic uniqueness of graphs (English)
0 references
8 September 1997
0 references
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\).
0 references
chromatic polynomial
0 references
chromatic uniqueness
0 references
chromatically unique graphs
0 references