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


Split and balanced colorings of complete graphs
Authors:Paul Erds  Andrs Gyrfs
Institution:

a Institute of Mathematics, Hungarian Academy of Sciences, Hungary

b Computer and Automation Institute, Hungarian Academy of Sciences, Hungary

Abstract:An (r, n)-split coloring of a complete graph is an edge coloring with r colors under which the vertex set is partitionable into r parts so that for each i, part i does not contain Kn in color i. This generalizes the notion of split graphs which correspond to (2, 2)-split colorings. The smallest N for which the complete graph KN has a coloring which is not (r, n)-split is denoted by ?r(n). Balanced (r,n)-colorings are defined as edge r-colorings of KN such that every subset of N/r] vertices contains a monochromatic Kn in all colors. Then gr(n) is defined as the smallest N such that KN has a balanced (r, n)-coloring. The definitions imply that fr(n) less-than-or-equals, slant gr(n). The paper gives estimates and exact values of these functions for various choices of parameters.
Keywords:Balanced coloring  Split graphs  Vertex set
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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