کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650504 | 1342490 | 2008 | 15 صفحه PDF | دانلود رایگان |
The chromatic capacity χcap(G)χ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→Nf:N→N such that χcap(G)⩾f(χ(G))χcap(G)⩾f(χ(G)) for almost every graph G , where χχ denotes the chromatic number. We show that for any positive integers n and k with k⩽n/2k⩽n/2 there exists a graph G with χ(G)=nχ(G)=n and χcap(G)=n-kχcap(G)=n-k, extending a result of Greene. We obtain bounds on χcap(Knr) that are tight as r→∞r→∞, where Knr 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 χcap(G)+1=χ(G)=pχcap(G)+1=χ(G)=p that contains no odd cycles of length less than q.
Journal: Discrete Mathematics - Volume 308, Issue 11, 6 June 2008, Pages 2134–2148