Critically and minimally cochromatic graphs

摘要

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 boolean OR K-2 boolean OR center dot center dot center dot boolean OR Kn-1 boolean OR G is a critically n-cochromatic graph if and only if G is K-n(n >= 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 boolean OR K-2 boolean OR center dot center dot center dot boolean OR Kn-1 boolean OR G (n >= 2) is minimally n-cochromatic if and only if G is K-n or K-n boolean OR (K-p) over bar for p >= 1. We close by giving some properties of minimally n-cochromatic graphs.