Chromatic capacity and graph operations Original Research Article

The chromatic capacity image of a graph G is the largest k for which there exists a k-coloring of the edges of G such that, for every coloring of the vertices of G with the same colors, some edge is colored the same as both its vertices. We prove that there is an unbounded function image such that image for almost every graph G, where image denotes the chromatic number. We show that for any positive integers n and k with image there exists a graph G with image and image, extending a result of Greene. We obtain bounds on image that are tight as image, where image is the complete n-partite graph with r vertices in each part. Finally, for any positive integers p and q we construct a graph G with image that contains no odd cycles of length less than q.