A lower bound on cochromatic number for line graphs of a kind of graphs (Q854573)

A \(t\)-cocoloring of a graph \(G\) is a partition of \(V(G)\) into \(t\) sets such that each set of the partition induces an empty graph or a complete graph. \(G\) is \(t\)-cocolorable if \(G\) has a \(t\)-cocoloring. The cochromatic number of \(G\), denoted \(z(G)\), is \(z(G)=\min\{t:G\) is \(t\)-cocolorable\}. \textit{P. Erdős, J. Gimbel} and \textit{H. J. Straight} [Eur. J. Comb. 11, 235--240 (1990; Zbl 0721.05020)] conjectured that if \(\omega(G)<5\) and \(z(G)>3\) then \(z(G)\geq\chi (G)-2\). It is shown here that if \(G\) is a line graph of a connected graph \(G\) with \(\omega(G)<5\) and \(G\neq K_4\), then \(z(G)\geq\chi(G)-2\), where \(\omega(G)\) is the clique number of \(G\).