彩色数の多項式限界 VI  4頂点経路を加える【JST・京大機械翻訳】

Chudnovsky Maria; Scott Alex; Seymour Paul; Spirkl Sophie

プレプリント

J-GLOBAL ID：202202216743505503 整理番号：22P0293024

彩色数の多項式限界 VI 4頂点経路を加える【JST・京大機械翻訳】

Polynomial bounds for chromatic number VI. Adding a four-vertex path

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (4件)： , , ,
資料名：
発行年： 2022年02月21日プレプリントサーバーでの情報更新日： 2023年03月22日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

クラス内のあらゆるグラフGが,ほとんどのf(ω(G))で色数を持ち,そこでは,ω(G)がGのクリーク数であるような関数fがあるならば,グラフのクラスはχ結合である。fが多項式であるならば,クラスは多項式的にχ結合される。Gy’arf’as-Sumner推定は,あらゆる森林Hに関して,Hフリーグラフ(Hの誘発コピーのないグラフ)のクラスがχ結合であると主張する。Hフリーグラフのクラスが多項式χ有界であるならば,より強い特性を満たすならば,森林Hは良い。非常に少数の森林は良いと知られている:例えば,それは5頂点経路のために開いている。実際,もし森林Hのあらゆる成分が良いならば,Hが良好であれば,特に,2つの4頂点経路の互いに素な結合が良好であることは知られていない。ここでは,Hが良好であるならば,Hと4頂点経路の互いに素な結合であるならば,後者を示した。また,H_1のあらゆる成分が良好で,H_2が任意の経路(またはブルーム)であり,次にH_1フリーとH_2フリーの両方であるグラフのクラスが多項式χ結合であることをより一般的な結果も証明した。【JST・京大機械翻訳】

, , , , , , , , ,
, , , , 【Automatic Indexing@JST】

グラフ理論基礎

, , , ,

前のページに戻る