Chromatic capacity and graph operations (Q2483394)

Let \(G\) be a simple graph. If the edges and the vertices of \(G\) are coloured simultaneously, an edge is called \textit{monochromatic} if its colour is the same as the colour of each of its endvertices. An edge colouring is \textit{compatible} with a vertex colouring if there is no monochromatic edge. If an edge colouring is such that there is no compatible vertex colouring using the same colour set, then it is an \textit{emulsion}, and is said to be \textit{emulsive}. The \textit{chromatic capacity} \(\chi_{cap}(G)\) of a graph \(G\) is the largest \(k\) for which there exists an emulsion using \(k\) colours. It is proved that there is an unbounded function \(f: N \to N\) such that \(\chi_{cap}(G)\geq f(\chi(G))\) for almost every graph \(G\). Moreover, it is showed that for any positive integer \(n\) and \(k\) with \(k\leq n/2\) there exist a graph \(G\) with \(\chi(G)=n\) and \(\chi_{cap}(G)=n-k\). Some bounds for the chromatic capacity of complete bipartite graphs and a construction of graphs with chromatic capacity \(\chi(G)-1\) are presented as well.