论文部分内容阅读
简单图G（y，E）的k-正常染色f称作G的k-2-距离染色，当且仅当任意w∈V（G），任意v,u∈N[w]，满足f（u）≠f（v）．得到了最大度为A的图类的2-距离色数的一个下界，χ^2（Δ=d）≥{（d/2＋1）^2,d≡0（mod 2）[（d＋1）（d＋3）]/4,d≡1（mod 2）并回答了文献[1]提出的问题：能否找到一常数C，使得χ^2（G）≤C△（G）对所有图G都成立．证明了这样的C是不存在的．