線形Ramsey数を持つグラフクラス【JST・京大機械翻訳】

Alecu Bogdan; Atminas Aistis; Lozin Vadim; Zamaraev Viktor

プレプリント

J-GLOBAL ID：202202221173975687 整理番号：22P0083583

線形Ramsey数を持つグラフクラス【JST・京大機械翻訳】

Graph classes with linear Ramsey numbers

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

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

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

グラフXのクラスに対するRamsey数R_X(p,q)は最小nであり,少なくともn頂点を持つXにおけるすべてのグラフはサイズpのクリークまたはサイズqの独立集合のいずれかを持つ。Ramsey数は,すべてのp,qに対してR_X(p,q)≦k(p+q)のような一定のkが存在するならば,Xにおいて線形である。本論文では,もしXが有限に多くの禁制誘導部分グラフによって定義される遺伝クラスであるならば,Xが森林を除外するならば,クリークとそれらの補完の互いに素な結合であるならば,Ramsey数はXにおいて線形であると推測した。著者らは,この予測の一部が,様々なクラスに対する「if」部分を検証することを,証明した。また,二部Ramsey数に対する線形性の概念を適用し,二部と非二者の場合の多くの類似性と相違を明らかにした。【JST・京大機械翻訳】

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

グラフ理論基礎

, ,

前のページに戻る