Uniquely cocolourable graphs

DOI10.1007/BF01788094MaRDI QIDQ1079577zbMATH OpenFDO

Authors Izak Broere, Marieta Burger

Publication date 1986

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01788094

zbMATH Keywords

colour classescomplete graphempty graphn-colourable graphuniquely colourable graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

A cocolouring of a graph G is a partition of the vertex set of G in such a way that each set of the partition induces an empty or a complete graph in G. The cochromatic number of G, denoted by z(G), is the minimum number of colours needed in any cocolouring of G. A graph G with \(z(G)=n\) is uniquely n-cocolourable if all n-cocolourings of G induce the same partition of V(G). In this paper it is proved that for each natural number n there are infinitely many uniquely n-cocolourable graphs and that the numbers of complete and empty colour classes can be prescribed. It is also shown that every n-cocolourable graph is an induced subgraph of a uniquely n-cocolourable graph.

Recommendations

• Critically cochromatic graphs
• On cocolourings and cochromatic numbers of graphs
• Some topics in cochromatic theory
• ON UNIQUELY -G k-COLOURABLE GRAPHS
• Critically and minimally cochromatic graphs

Cited in

(3)

• On Garlands in \(\chi\)-uniquely colorable graphs
• scientific article; zbMATH DE number 1439482 (Why is no real title available?)
• Unique Colorability and Clique Minors

This page was built for publication: Uniquely cocolourable graphs

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