Chromaticity of a family of \(K_ 4\) homeomorphs (Q1366777)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Chromaticity of a family of \(K_ 4\) homeomorphs |
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
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
0.9994484
0 references
0 references
0.97514623
0 references
0.97081757
0 references
0.96665657
0 references
0.9655461
0 references