禁止されたほとんど二部部分グラフを用いたグラフの彩色【JST機械翻訳】

Anderson James; Bernshteyn Anton; Dhawan Abhishek

プレプリント

J-GLOBAL ID：202202217883719127 整理番号：22P0303872

禁止されたほとんど二部部分グラフを用いたグラフの彩色【JST機械翻訳】

Coloring graphs with forbidden almost bipartite subgraphs

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

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

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

Alon,Krivelevich,およびSudakovは1999年に推測され,すべての有限グラフFに対して,Gが最大次数ΔのFフリーグラフであるときはいつでも,χ(G)≦傾斜(c(F)+o(1))Δ/logΔの量c(F)が存在する。Alon,Krivelevich,Sudakov自身によりこの予測が検証されてきた連結グラフFの最大クラスは,ほとんど2部グラフ(いくつかのt∈Nに対する完全3部グラフK_1,t,tの部分グラフ)から構成されている。しかしながら,c(F)に対する最適値は,そのようなグラフに対しても未知のままである。Bollob’asは,ランダム正則グラフを用いて,Fがサイクルを含むときc(F)≧傾斜1/2であることを示した。一方,Davies,Kang,Pirot,およびSereniは最近c(K_1,t,t)≦傾斜tの上限を確立した。これを一定に改善し,すべてのほとんど二分したグラフFに対してc(F)≦傾斜4を示した。この驚くべきことに,この予測のすべての既知のケースにおいて,Fから独立している境界を作って,c(F)がFから独立したいくつかの定数cによって常に有界であるという新規予測を著者らに導いた。また,筆者らはDP彩色(対応彩色としても知られる)の設定における筆者らの限界のより一般的バージョンを確立し,筆者らの結果のいくつかのアルゴリズム的帰結を考察した。【JST機械翻訳】

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

グラフ理論基礎

, , ,

前のページに戻る