Chromatic number versus chromatic number in graphs with bounded clique number (Q2640609): Difference between revisions

The cochromatic number \(z(G)\) of a graph \(G\) is the minimum number of sets into which the vertices of \(G\) can be partitioned so that each set is independent in \(G\) or induces a complete subgraph of \(G\). The present paper proves the existence ofa function \(f(n)\) with the following property: If \(G\) does not contain a complete \(n\)-graph \(K_n\) and \(G\neq K_{n-1}\), then the usual chromatic number \(\chi(G)\) is at most \(z(G)+f(n)\). Moreover it is proved that \(f(n)\) is exponential in \(n\) and that \(f(3)=1\) and \(f(4)=1\).