A new method for proving chromatic uniqueness of graphs

DOI10.1016/S0012-365X(96)00078-7MaRDI QIDQ1363698zbMATH OpenOpenAlexFDO

Authors Ru Ying Liu, Lianchang Zhao

Publication date 8 September 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(96)00078-7

zbMATH Keywords

chromatic polynomial chromatic uniqueness chromatically unique graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

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\).

Recommendations

Cites work

Cited in

(15)

This page was built for publication: A new method for proving chromatic uniqueness of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1363698)