Chromaticity of a family of \(K_{4}\)-homeomorphs (Q1850049): Difference between revisions

A graph is chromatically unique if it is uniquely determined up to isomorphism by its chromatic polynomial. A \(K_4\)-homeomorph is a subdivision of the complete graph \(K_4\), i.e. a graph consisting of six paths, also called \(*\)-paths, joining four vertices of degree three. It is well known that almost all \(K_4\)-homeomorphs are chromatically unique [\textit{W. Li}, Ars Comb. 23, 13-35 (1987; Zbl 0644.05020)]. The paper under review studies the family of \(K_4\)-homeomorphs having the property that all but two adjacent \(*\)-paths have length more than one. The authors prove a necessary and sufficient condition, formulated in terms of lengths of \(*\)-paths, for the graphs in this family to be chromatically unique. This complements a result of \textit{S.~Xu} [Discrete Math. 117, 293-297 (1993; Zbl 0781.05022)] who obtained a similar characterization for the family of \(K_4\)-homeomorphs with two nonadjacent \(*\)-paths of length one.