首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Chromatic capacity and graph operations
Authors:Jack Huizenga
Institution:Department of Mathematics, Harvard University, Cambridge, MA 02138, USA
Abstract: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 f:NN 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 k?n/2 there exists a graph G with χ(G)=n and χcap(G)=n-k, extending a result of Greene. We obtain bounds on View the MathML source that are tight as r→∞, where View the MathML source 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.
Keywords:Chromatic capacity  Emulsive edge coloring  Compatible vertex coloring  Split coloring  Lexicographic product
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号