グラフにおける長い誘導経路【Powered by NICT】

Esperet Louis; Esperet Louis; Lemoine Laetitia; Maffray Frederic; Maffray Frederic

文献

J-GLOBAL ID：201802261208626382 整理番号：18A0329297

グラフにおける長い誘導経路【Powered by NICT】

Long induced paths in graphs

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=18A0329297&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=18A0329297&from=J-GLOBAL&jstjournalNo=A1229A") }}

著者 (5件)： , , , ,
資料名：
巻： 62 ページ： 1-14 発行年： 2017年
JST資料番号： A1229A ISSN： 0195-6698 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：オランダ (NLD) 言語：英語 (EN)

nの頂点上の全ての3-連結平面グラフがΩ(logn)頂点,これは最良可能であるとlog lognの乗法因子による最良の既知の下限を改善する上に誘起された経路を含むことを証明した。nの頂点上の経路であるようないかなる平面グラフ(より一般的には,固定表面上の埋込み可能任意のグラフ)も,Ω(logn)頂点上の誘導経路を含むと結論した。任意のk,nの頂点上の経路を持つ任意のk-縮退グラフもΩ((logn)C(k))の頂点上の誘導経路を含むようは正の定数C(k)であることを予想した。はこの順序は最良可能である(既に弦グラフのための)ことを示す例を提供し,区間グラフの場合に予想を証明した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

, , ,
, 【Automatic Indexing@JST】

グラフ理論基礎

, ,

前のページに戻る