少数閉グラフクラスとそれを超えた長い誘導経路【JST・京大機械翻訳】

Hilaire Claire; Raymond Jean-Florent

プレプリント

J-GLOBAL ID：202202216337766541 整理番号：22P0026117

少数閉グラフクラスとそれを超えた長い誘導経路【JST・京大機械翻訳】

Long induced paths in minor-closed graph classes and beyond

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

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

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

本論文では,次数nの経路を持つk以下の経路幅のあらゆるグラフが,少なくとも1/3n ̄1/kのオーダーの誘起経路を持つことを示した。これは,有界クリーク数の区間グラフに対して,Esperet,LemoineおよびMaffray(2016)によって得られた多対数限界の指数関数的改善および一般化である。この結果を上限で補完した。次に,この結果を用いて,次の2つの一般化,すなわち,次数nの経路を持つk以下の木幅の任意のグラフは,少なくとも1/4(logn) ̄1/kのオーダーの誘起経路を含む;トポロジカルマイナーの下で閉じるあらゆる非自明グラフクラスに対して,次数nの経路を持つこのクラスからのあらゆるグラフが少なくとも(logn) ̄dのオーダーの誘起経路を含むように,一定のd→∞(0,1)がある。また,トポロジカルマイナーの下で閉じたグラフクラスを超えてこれらの結果を記述した。【JST・京大機械翻訳】

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

グラフ理論基礎

, , ,

前のページに戻る