Chromaticity of series-parallel graphs
If \(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.
- A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
- An introduction to chromatic polynomials
- Chromatic polynomials of generalized trees
- Chromatic polynomials, polygon trees, and outerplanar graphs
- Chromatic uniqueness of the generalized -graph
- Classes of chromatically equivalent graphs and polygon trees
- scientific article; zbMATH DE number 4091530 (Why is no real title available?)
- scientific article; zbMATH DE number 1465165 (Why is no real title available?)
- On chromatic equivalence of graphs
- On trees of polygons
- The chromaticity of s-bridge graphs and related graphs
- The search for chromatically unique graphs
- Topology of series-parallel networks
- Classes of chromatically equivalent graphs and polygon trees
- The search for chromatically unique graphs. II
- Chromatic equivalence classes of certain generalized polygon trees
- A bibliography on chromatic polynomials
- List total colorings of series-parallel graphs
- Multicolorings of series-parallel graphs
- On minimum average stretch spanning trees in polygonal 2-trees
- Generalized trees and their applications
- Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs
- The chromaticity of certain cycles with edges
- scientific article; zbMATH DE number 528795 (Why is no real title available?)
- scientific article; zbMATH DE number 2197936 (Why is no real title available?)
This page was built for publication: Chromaticity of series-parallel graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1918563)
