r-Strong edge colorings of graphs

S. Akbari, H. Bidkhori and N. Nosrati
Discrete Mathematics
Volume 306, Issue 23 , 6 December 2006, Pages 3005-3010
http://dx.doi.org/10.1016/j.disc.2004.12.027

グラフGと自然数rが与えられる．
グラフGの辺彩色で，距離がr以内にある2つの頂点に接続する辺の色の集合が異なっているものを考える．
そのような辺彩色の最小色数をχ'_s(G,r)とする．
予想として，「頂点数が6以上で孤立辺を持たないグラフGに対してχ'_s(G,1)≦Δ(G)+2」というものがある．
Zhang, Liu and Wang (2002) によってGが頂点数3以上の木であるとき、
χ'_s(G,1)≦Δ(G)+1が証明された．
この論文では、Gがそのようなグラフのときχ'_s(G,2)≦Δ(G)+1が成り立つこと、
Gが最大次数3以上の木の場合χ'_s(G,3)≦2Δ(G)-1が成り立つことを示している．
ちなみに，論文のタイトルを数学記号で始めるのはあまり好ましくない．
この論文なら頭に「On」でもつけておけばそれが防げた．