誘導部分グラフとツリー分解 IV  (偶穴,ダイヤモンド,ピラミッド)フリーグラフ【JST・京大機械翻訳】

Abrishami Tara; Chudnovsky Maria; Hajebi Sepehr; Spirkl Sophie

プレプリント

J-GLOBAL ID：202202205116259643 整理番号：22P0303425

誘導部分グラフとツリー分解 IV (偶穴,ダイヤモンド,ピラミッド)フリーグラフ【JST・京大機械翻訳】

Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs

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

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

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

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

グラフGの穴は,少なくとも4つの長さの誘導サイクルであり,偶数穴は偶数長の穴である。ダイヤモンドはエッジを除去することによって完全なグラフK_4から得られたグラフである。ピラミッドは,基底と呼ばれる三角形,頂点と呼ばれる頂点,および頂点および互いに素に開始する3つの内部結合経路から成るグラフであり,それぞれ,頂点を基底の頂点に接続する。グラフのファミリーHに対して,Gの誘起部分グラフがHのメンバーに同形でないならば,グラフGはHフリーである。Cameron,da Silva,Huang,およびVu vskovi’cは,(偶数穴,三角形)フリーグラフが,ほとんどの5で木幅を持ち,それは,より大きなクリーク数の偶数穴のないグラフの木幅を研究することを動機づけることを証明した。SintiariとTrotignonは,任意に大きな木幅の(偶数穴,ピラミッド,K_4)フリーグラフの構築を提供した。ここでは,全てのtに対して(正孔,ピラミッド,ダイヤモンド,K_t)フリーグラフが有界ツリー幅を持つことを示した。SintiariとTrotignonにより構築されたグラフはダイヤモンドを含み,その結果,ダイヤモンドを除外しないならば,結果は誤っているという意味でシャープである。著者らの主な結果は,実際により一般的であり,ある車輪と3経路構成,ダイヤモンド,および固定完全グラフを除くグラフにおいて,ツリー幅が有界である。証明は,このシリーズの以前の論文と同様の「非交差分解」法を使用する。しかし,以前の論文では,有界程度は有界木幅を証明するための必要条件であった。本論文の結果は,「非交差分解」の方法を用いて,非有界最大度合のグラフクラスにおける有界ツリー幅を証明した。【JST・京大機械翻訳】

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

グラフ理論基礎

, , , , ,

前のページに戻る