Chromatic capacity and graph operations

详细信息    查看全文

• 作者：Jack Huizenga
• 关键词：Chromatic capacity ; Emulsive edge coloring ; Compatible vertex coloring ; Split coloring ; Lexicographic product
• 刊名：Discrete Mathematics
• 出版年：2008
• 出版时间：6 June 2008
• 年：2008
• 卷：308
• 期：11
• 页码：2134-2148
• 全文大小：285 K

文摘

The chromatic capacity χ_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 such that χ_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 kn/2 there exists a graph G with χ(G)=n and 0b36abefbaf5915eb5f3bb778c74f8d6"" title=""Click to view the MathML source"" alt=""Click to view the MathML source"">χ_cap(G)=n-k, extending a result of Greene. We obtain bounds on 90b05c31def0a96e8a1dfbf118619c""> that are tight as r→∞, where 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 that contains no odd cycles of length less than q.