On the chromatic equivalence class of graphs

DOI10.1016/S0012-365X(97)81814-6MaRDI QIDQ1377862zbMATH OpenFDO

Authors Gek L. Chia

Publication date 10 August 1999

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(97)81814-6

zbMATH Keywords

chromatic equivalence classchromatic polynomial

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

Let \(P(G, \lambda)\) denote the chromatic polynomial of a graph \(G\). Two graphs \(G\) and \(H\) are chromatically equivalent if \(P(G,\lambda) = P(H,\lambda)\). The chromatic equivalence class of \(G\) consists of all graphs chromatically equivalent to \(G\). For example, the chromatic equivalence class of a tree consists of exactly all other trees of the same order. The join of two graphs \(G\) and \(H\) is obtained by taking a disjoint copy of each graph and adding edges from every vertex of \(G\) to every vertex of \(H\). The author determines the class of all graphs in the chromatic equivalence class of the join of \(m\) copies of paths each of length 3. He also gives two operations, which when applied to graphs in the chromatic equivalence class of \(G\), give all graphs with chromatic polynomial \(\lambda P(G,\lambda)\). A similar result is given for all graphs with chromatic polynomial \((\lambda -1) P(G,\lambda)\).

Recommendations

• The chromaticity of certain cycles with edges
• Chromatic equivalence classes of certain generalized polygon trees. III
• Classes of chromatically equivalent graphs and polygon trees

Cites work

• A note on chromatic uniqueness of graphs
• An introduction to chromatic polynomials
• Chromaticity of two-trees
• Cutpoints and the chromatic polynomial
• scientific article; zbMATH DE number 3127542 (Why is no real title available?)
• scientific article; zbMATH DE number 3904612 (Why is no real title available?)
• scientific article; zbMATH DE number 4099332 (Why is no real title available?)
• scientific article; zbMATH DE number 4108817 (Why is no real title available?)
• scientific article; zbMATH DE number 38309 (Why is no real title available?)
• scientific article; zbMATH DE number 151783 (Why is no real title available?)
• scientific article; zbMATH DE number 3458642 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• On graphs in which any pair of colour classes but one induces a tree
• On the chromatic equivalence class of a family of graphs
• On the chromaticity of certain subgraphs of a q-tree
• On trees of polygons
• Onq-trees
• The chromaticity of complete bipartite graphs with at most one edge deleted

Cited in

(15)

• Classes of chromatically unique or equivalent graphs
• Classes of chromatically equivalent graphs and polygon trees
• On the chromatic equivalence class of a family of graphs
• Chromatic equivalence classes of certain generalized polygon trees
• A bibliography on chromatic polynomials
• Chromatic equivalence classes of certain generalized polygon trees. III
• Classes of graphs with \(e\)-positive chromatic symmetric function
• scientific article; zbMATH DE number 5073889 (Why is no real title available?)
• The chromaticity of certain cycles with edges
• scientific article; zbMATH DE number 5631913 (Why is no real title available?)
• Equivalent classes for K₃-gluings of wheels
• scientific article; zbMATH DE number 812060 (Why is no real title available?)
• scientific article; zbMATH DE number 892216 (Why is no real title available?)
• scientific article; zbMATH DE number 2192207 (Why is no real title available?)
• Pairs of chromatically equivalent graphs

This page was built for publication: On the chromatic equivalence class of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377862)