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 $criticallyn-cochromatic$ if $z(G–v)=n–1$ for each vertex $v$ of $G$, and $minimallyn-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\ge 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\ge 2)$ is minimally $n$-cochromatic if and only if $G$ is $K_n$ or $\overline{K_{n-1}}\cup \overline{K_p}$ for $p\ge 1$. We close by giving some properties of minimally $n$-cochromatic graphs.