List edge and list total colorings of planar graphs without 4-cycles

Jianfeng Hou, Guizhen Liu and Jiansheng Cai
Theoretical Computer Science
Volume 369, Issues 1-3, 15 December 2006, Pages 250-255
http://dx.doi.org/10.1016/j.tcs.2006.08.043

グラフの彩色に関するはなし．

「List Coloring Conjecture」としてよく知られている予想は，グラフの辺染色数とリスト辺染色数は常に等しいというものであり，それに似た予想として，グラフのトータル染色数とリストトータル染色数が常に等しいというものがある．
この論文では平面的グラフを考え，また，グラフが長さ4からkまでの閉路を含まない場合にリスト辺染色数とリストトータル染色数がどうなるか調べて，上記予想の解決に向けた貢献をしている．