zbMATH — the first resource for mathematics

Chromaticity of a family of \(K_ 4\)-homeomorphs. (English) Zbl 0781.05022
Let \(G\) be a graph and \(P(G,\lambda)\) be its chromatic polynomial. If \(P(G,\lambda)=P(H,\lambda)\) implies \(H\) is isomorphic to \(G\), then \(G\) is said to be chromatically unique. It is well known that the cycle and the cycle with one chord, are both chromatically unique. If a cycle has two chords and they do not cross, then the graph is a polygon tree and is not chromatically unique.
In this paper the chromaticity of a graph consisting of a cycle with two crossing chords is discussed and necessary and sufficient conditions are given for it to be chromatically unique. Each such a graph can be viewed as a \(K_ 4\)-homeomorph \(K_ 4(w,x,y,z,1,1)\) and it is proved that this graph is not chromatically unique if and only if it is \(K_ 4(a+2,a,2,2,1,1)\) or \(K_ 4(a+1,a+3,a,2,1,1)\) or \(K_ 4(a+2,b,a,2,1,1)\) where \(a \geq 1\), \(b \geq 1\) and \(a+b \neq 2\).

05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
Full Text: DOI
[1] Chao, C.Y.; Whitehead, E.G., On chromatic equivalence of graphs, ()
[2] Chao, C.Y.; Zhao, L.C., Chromatic polynomials of a family of graphs, Ars combin., 15, 111-129, (1983) · Zbl 0532.05027
[3] Weiming, Li, Almost every K4 homeomorph is chromatically unique, Ars combin., 23, 13-36, (1987) · Zbl 0644.05020
[4] Whitehead, E.G.; Zhao, L.C., Chromatic uniqueness and equivalence of K4 homeomorphs, J. graph theory, 8, 355-364, (1984) · Zbl 0555.05035
[5] Xu, S., A lemma in studying chromaticity, Ars combin., 32, 315-318, (1991) · Zbl 0753.05039
[6] S. Xu, Classes of chromatically equivalent graphs and polygon trees, to appear. · Zbl 0813.05030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.