Chromatic Number Versus Cochromatic Number in Graphs with Bounded Clique Number

Given a simple graph G = (V, E), a subset U of V is called a clique if it induces a complete subgraph of G, and is called an independent set if it induces an empty subgraph of G. The cochromatic number z(G) of G is the minimum number of sets into which V can be partitioned so that each set is independent or a clique. Then z(G) is bounded above by the familiar chromatic number χ(G) of G. Let ω(G) denote the maximum cardinality among the cliques of G, and let n be an integer greater than 2. In this paper we explore the following question: Is there a function f(n) of n such that, if G has ω(G) < n and is not the complete graph of order n - 1, then χ(G) ⩽ z(G) + f(n)? Some bounds on f(n) are obtained and, in particular, it is shown that f(3) = 0 and f(4) = 1