Critically and Minimally Cochromatic Graphs

Abstract

The cochromatic number of a graph \(G\), denoted by \(z(G)\), is the fewest number of parts we need to partition \(V(G)\) so that each part induces in \(G\) an empty or a complete graph. A graph \(G\) with \(z(G) = n\) is called \({critically n-cochromatic}\) if \(z(G – v) = n – 1\) for each vertex \(v\) of \(G\), and \({minimally n-cochromatic}\) if \(z(G – e) = n – 1\) for each edge \(e\) of \(G\).

We show that for a graph \(G\), \(K_{1} \cup G \cup K_{2} \cup \cdots \cup K_{n-1} \cup G\) is a critically \(n\)-cochromatic graph if and only if \(G\) is \(K_{n}\), \((n \geq 2)\). We consider general minimally cochromatic graphs and obtain a result that a minimally cochromatic graph is either a critically cochromatic graph or a critically cochromatic graph plus some isolated vertices. We also prove that given a graph \(G\), then \(K_{1} \cup G \cup K_{2} \cup \cdots \cup K_{n-1} \cup G\) \((n \geq 2)\) is minimally \(n\)-cochromatic if and only if \(G\) is \(K_{n}\) or \(\overline{K_{n-1}} \cup \overline{K_{p}}\) for \(p \geq 1\). We close by giving some properties of minimally \(n\)-cochromatic graphs.