誘導部分グラフとツリー分解 V  大きな頂点の小成分【JST・京大機械翻訳】

Alecu Bogdan; Chudnovsky Maria; Vuskovic Kristina

プレプリント

J-GLOBAL ID：202202204330786182 整理番号：22P0327525

誘導部分グラフとツリー分解 V 大きな頂点の小成分【JST・京大機械翻訳】

Induced subgraphs and tree decompositions V. Small components of big vertices

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

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

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

Aboulker,Adler,Kim,Sintiari,およびTrotignonは,有界最大次数と大きな木幅を有するあらゆるグラフが,大きな細分壁の誘導部分グラフ,大きな細分壁,または線グラフとして含まれなければならないことを推測する。この予想はKorhonenにより最近証明されたが,一般的事例(有界最大度条件なし)における有界木幅に対する障害物の同定問題は広い開放性のままである。SintiariとTrotignon,およびDaviesによって,「通常疑う」を避ける大きな木幅の構造例を構築した。このノートでは,大きな木幅をもたらすこれらの例の特徴をより良く分離することを目的とした。この目的のために,以下の結果を証明した。Gをグラフとし,少なくとも3度の頂点集合上でGによって誘起されたグラフの最大接続成分のサイズに対してγ(G)を書き込む。γ(G)が小さい場合,Gの木幅が大きい場合,Gは大きい細分壁あるいは大きな細分壁の線グラフを含む必要がある。この結果は,Daviesの例によって証明されたように,γ(G)の定義において,もし3つをより大きな数で置換するならば,結論が失敗するという意味で,最良の可能性である。【JST・京大機械翻訳】

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

グラフ理論基礎

, , ,

前のページに戻る