Chromatic capacity and graph operations

The chromatic capacity chi(cap)(G) 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 f: N -> N such that chi(cap)(G) >= f (chi(G)) for almost every graph G, where chi denotes the chromatic number. We show that for any positive integers n and k with k <= n/2 there exists a graph G with chi(G) = n and chi(cap)(G) = n - k, extending a result of Greene. We obtain bounds on chi(cap)(K-n(r)) that are tight as r -> infinity, where K-n(r) 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 chi(cap)(G) + 1 = chi(G) = p that contains no odd cycles of length less than q. (C) 2007 Elsevier B.V. All rights reserved.