Some relations among term rank, clique number and list chromatic number of a graph

Saieed Akbari and Hamid-Reza Fanai
Discrete Mathematics
Volume 306, Issue 23 , 6 December 2006, Pages 3078-3082
http://dx.doi.org/10.1016/j.disc.2004.11.028

グラフGの隣接行列の階数をrk(G)と書いて，隣接行列の中の1を適当な実数に置き換えたときの階数の最大値を項階数と呼んでRk(G)と書くことにする．
1976年にvan NuffelenはGが辺を持つときχ(G)≦rk(G)が成り立つという予想を立てたが，これが成り立たないことをAlon and Seymour (1989) は証明した．(χ(G)はGの染色数．)
しかしFishkind and Kotlov (2002) はχ(G)≦Rk(G)が成り立つことを証明した．
この論文では彼らの結果を改善してχ_l(G)≦(rk(G)+Rk(G))/2が成り立つことを証明している．
ただし，χ_l(G)はGのリスト染色数である．