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


Locally restricted colorings
Authors:Ivo Blöchliger  Dominique de Werra
Institution:Ecole Polytechnique Fédérale de Lausanne (EPFL), Chaire de recherche opérationnelle sud-est, CH-1015 Lausanne, Switzerland
Abstract:We consider the following problem: given suitable integers χ and p, what is the smallest value ρ such that, for any graph G with chromatic number χ and any vertex coloring of G with at most χ+p colors, there is a vertex v such that at least χ different colors occur within distance ρ of v? Let ρ(χ,p) be this value; we show in particular that ρ(χ,p)?⌈p/2⌉+1 for all χ,p. We give the exact value of ρ when p=0 or χ?3, and (χ,p)=(4,1) or (4,2).
Keywords:Chromatic number  Graph coloring  Locally restricted colorings
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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