k-ColoringはChromatic Numberの計算よりも高速である

コンピュータサイエンス > データ構造とアルゴリズム arXiv:2607.25973 (cs) [2026年7月28日提出] タイトル:k-ColoringはChromatic Numberの計算よりも高速である 著者:Or Zamir 「k-ColoringはChromatic Numberの計算よりも高速である」というタイトルのPDFを表示 PDFを表示 HTML（実験的） 概要： n頂点グラフのk-Coloringが、固定されたkに対して(2-εk)^n時間で実行されるランダム化アルゴリズムを持つことを証明します。ここで、εk>0は全ての固定kに対して成り立ちます。以前は、[Björklund, Husfeldt, Koivisto, SICOMP 2009]によるChromatic Numberを計算する一般的なO*(2^n)時間アルゴリズムよりも高速な解法が存在するのは、k≤6の場合のみでした。 私たちは、[Zamir, ICALP 2021]による(k+2)-Coloringからk-list-coloringへの還元と、[Zamir, STOC 2023]におけるハイパーグラフコンテナベースのアプローチからのツールを一般化・組み合わせることで、この長年の未解決問題を解決します。これに加えて、長いリストと短いリストが混在するリスト彩色インスタンスのための新しいアルゴリズムを組み合わせることで、固定パレット上での(k+1)-list-coloringからk-list-coloringへの反復可能な還元が得られます。 件名：データ構造とアルゴリズム (cs.DS) 引用形式：arXiv:2607.25973 [cs.DS] (またはこのバージョンについてはarXiv:2607.25973v1 [cs.DS]) https://doi.org/10.48550/arXiv.2607.25973 詳細はこちらをご覧ください arXiv発行DOI（登録保留中）DataCite経由 提出履歴 投稿者：Or Zamir [メールを表示] [v1] 火曜日、2026年7月28日 16:53:58 UTC (47 KB) 全文リンク： 論文にアクセス：Or Zamirによる「k-ColoringはChromatic Numberの計算よりも高速である」というタイトルのPDFを表示 PDFを表示 HTML（実験的） TeXソース ライセンスを表示 現在の閲覧コンテキスト：cs.DS < 前 | 次 > 新しい | 最近 | 2026-07 閲覧を次のように変更：cs 参考文献と引用 NASA ADS Google Scholar Semantic Scholar エクスポート BibTeX引用 読み込み中... BibTeX形式の引用 × 読み込み中... 提供元データ： ブックマーク 書誌ツール 書誌および引用ツール 書誌エクスプローラー 書誌エクスプローラーを切り替える（書誌エクスプローラーとは何ですか？） コネクテッドペーパー コネクテッドペーパーを切り替える（コネクテッドペーパーとは何ですか？） Litmaps Litmapsを切り替える（Litmapsとは何ですか？） scite.ai sciteスマート引用を切り替える（sciteスマート引用とは何ですか？） コード、データ、メディア この論文に関連するコード、データ、メディア alphaXiv alphaXivを切り替える（alphaXivとは何ですか？） コードへのリンク CatalyzeX 論文用コードファインダー（CatalyzeXとは何ですか？） DagsHub DagsHubを切り替える（DagsHubとは何ですか？） GotitPub Gotit.pubを切り替える（GotitPubとは何ですか？） Huggingface Hugging Faceを切り替える（Huggingfaceとは何ですか？） ScienceCast ScienceCastを切り替える（ScienceCastとは何ですか？） デモ デモ Replicate Replicateを切り替える（Replicateとは何ですか？） Spaces Hugging Face Spacesを切り替える（Spacesとは何ですか？） Spaces TXYZ.AIを切り替える（TXYZ.AIとは何ですか？） 関連論文 レコメンダーおよび検索ツール 影響力フラワーへのリンク 影響力フラワー（影響力フラワーとは何ですか？） コアレコメンダー COREレコメンダーを切り替える（COREレコメンダーとは何ですか？） 著者 会場 機関 トピック arXivLabsについて arXivLabs：コミュニティ協力者との実験的なプロジェクト arXivLabsは、協力者がarXivの新しい機能を直接ウェブサイト上で開発・共有できるフレームワークです。arXivLabsと協力する個人および組織は、オープンさ、コミュニティ、卓越性、ユーザーデータプライバシーという私たちの価値観を受け入れ、遵守しています。arXivはこの価値観にコミットしており、それらを遵守するパートナーのみと協力します。 コミュニティに価値をもたらすプロジェクトのアイデアがありますか？arXivLabsの詳細をご覧ください。 この論文の著者のうち、推薦者は誰ですか？ MathJaxを無効にする（MathJaxとは何ですか？）