Chromaticity of a family of \(K_ 4\) homeomorphs (Q1366777)

From MaRDI portal





scientific article; zbMATH DE number 1061982
Language Label Description Also known as
English
Chromaticity of a family of \(K_ 4\) homeomorphs
scientific article; zbMATH DE number 1061982

    Statements

    Chromaticity of a family of \(K_ 4\) homeomorphs (English)
    0 references
    0 references
    16 March 1998
    0 references
    A (simple) graph \(G\) is called chromatically unique if any graph with the same polynomial as \(G\) must be isomorphic to \(G\). In [\textit{W. Li}, Almost every \(K_4\) homeomorph is chromatically unique, Ars Comb. 23, 13-36 (1987; Zbl 0644.05020)] it was shown that a \(K_4\)-homeomorph is chromatically unique if at least four of the six paths joing two vertices of degree 3 are edges, or if exactly three of these paths are edges and they form a triangle. The article under review states and proves a necessary and sufficient condition for a \(K_4\)-homeomorph exactly three of whose paths are edges to be chromatically unique, thereby solving two of the problems posed in [\((*)\) \textit{K. M. Koh} and \textit{K. L. Teo}, The search for chromatically unique graphs, Graphs Comb. 6, No. 3, 259-285 (1990; Zbl 0727.05023)]. The authors also claim to have proved a similar result about \(K_4\)-homeomorphs such that two nonadjacent paths are edges, and they derive a solution to a third problem in \((*)\), but the reviewer was unable to find either a proof of this result or a reference thereto.
    0 references
    homeomorphs
    0 references
    chromatic polynomials
    0 references
    chromatically unique
    0 references

    Identifiers