Vuの予想に向けて

2002年、Vuは、最大次数Δおよび最大共次数がせいぜいζΔのグラフの彩色数がせいぜい(ζ+o(1))Δであると予想しました。その重要性にもかかわらず、この予想は広く未解決のままです。これまでに得られた唯一の直接的な進展は、「密な領域」において、ζが1に近い場合にHurley、de Verclos、およびKangによって得られました。本論文では、Vuが関心を持つ主な場合である希薄な領域ζ 1における最初の進展を提供します。すべてのζ^-32Δ、ζ₀のもとで、ζ₀ > 0が存在することを示します。もしGが最大次数Δおよび最大共次数がせいぜいζΔのグラフであれば、χ(G)は(ζ^{1/32} + o(1))Δを満たします。これは、任意のs頂点の共通隣接点が制約されていることのみを仮定するより一般的な結果から導かれます。我々のより一般的な結果は、リスト彩色の設定にも拡張され、独自の興味を引きます。