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 等数据库收录! |
|