Chromaticity of series-parallel graphs.

*(English)*Zbl 0856.05035If \(P(G, \lambda)\) denotes the chromatic polynomial of a graph \(G\), two graphs \(G\) and \(H\) are said to be \(\chi\)-equivalent, written \(G \sim H\), if \(P(G, \lambda) = P (H, \lambda)\). Any equivalence class induced by \(\sim\) is called a \(\chi\)-equivalence class. A \(k\)-gon tree is obtained by edge-gluing a set of cycles each of order \(k\) successively. A graph is called a generalised polygon tree if it is a subdivision of a \(k\)-gon tree. Alternatively, a generalised polygon tree can be viewed as a 2-connected simple series-parallel graph (sp graph). In this paper some new chromatic invariants for sp graphs are introduced and it is proved that the class of polygon trees is a \(\chi\)-equivalence class. A class of sp graphs, called \(\Theta_k\)-gons, is shown to be closed under \(\chi\)-equivalence and some classes of \(\Theta_k\)-gons are identified to possess the same property; one of them is the class of \(k\)-gon trees.

Reviewer: I.Tomescu (Bucureşti)

##### MSC:

05C15 | Coloring of graphs and hypergraphs |

##### Keywords:

chromatic polynomial; generalised polygon tree; series-parallel graph; chromatic invariants
PDF
BibTeX
XML
Cite

\textit{K. M. Koh} and \textit{C. P. Teo}, Discrete Math. 154, No. 1--3, 289--295 (1996; Zbl 0856.05035)

Full Text:
DOI

##### References:

[1] | Chao, C.Y.; Li, N.Z., On trees of polygons, Arch. math., 45, 180-185, (1985) · Zbl 0575.05027 |

[2] | Chao, C.Y.; Whitehead, E.G., On chromatic equivalence of graphs, (), 121-131 |

[3] | Dirac, G.A., A property of 4-chromatic graphs and some results on critical graphs, J. London math. soc., 27, 85-92, (1952) · Zbl 0046.41001 |

[4] | Duffin, R.J., Topology of series-parallel networks, J. math. analy. appl., 10, 303-318, (1965) · Zbl 0128.37002 |

[5] | Koh, K.M.; Teo, K.L., The search for chromatically unique graphs, Graphs combin., 6, 259-285, (1990) · Zbl 0727.05023 |

[6] | Koh, K.M.; Teo, C.P., Some results on chromatically unique graphs, (), 258-262 · Zbl 0940.05502 |

[7] | Loerinc, B., Chromatic uniqueness of the generalised θ-graph, Discrete math., 23, 313-316, (1978) · Zbl 0389.05034 |

[8] | Read, R.C., An introduction to chromatic polynomials, J. combin. theory, 4, 52-71, (1968) · Zbl 0173.26203 |

[9] | Read, R.C.; Tutte, W.T., Chromatic polynomials, (), 15-42 · Zbl 0667.05022 |

[10] | Wakelin, C.D.; Woodall, D.R., Chromatic polynomials, polygon trees, and outerplanar graphs, J. graph theory, 16, 459-466, (1992) · Zbl 0778.05074 |

[11] | Whitehead, E.G., Chromatic polynomials of generalized trees, Discrete math., 72, 391-393, (1988) · Zbl 0659.05045 |

[12] | S.J. Xu, Classes of chromatically equivalent graphs and polygon trees, Discrete Math., to appear. · Zbl 0813.05030 |

[13] | S.J. Xu and J.J. Liu, The chromaticity of s-bridge graphs and related graphs, submitted. · Zbl 0814.05036 |

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.