A counterexample to the Alon-Saks-Seymour conjecture and related problems

Hao Huang, Benny Sudakov
ECCC TR10-026 http://eccc.hpi-web.de/report/2010/026/

Alon-Saks-Seymour予想はグラフに関する予想で，グラフGの辺集合がk個の完全二部グラフに分割できれば，Gの染色数はk+1以下になる，というものである．長い間何も進展の無かったこの予想に対する反例を与えたのがこの論文．どのようにしてこういう例が思いつくのかよく分からないけれども，驚いた．