固定長の二色経路を避けるグラフの彩色【JST・京大機械翻訳】

Kirtisoglu Alaittin; OEzkahya Lale

プレプリント

J-GLOBAL ID：202202203836756030 整理番号：22P0216278

固定長の二色経路を避けるグラフの彩色【JST・京大機械翻訳】

Coloring of Graphs Avoiding Bicolored Paths of a Fixed Length

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

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

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

サブグラフの固定ファミリーの任意の二色コピーを含むことなく,色に対する色の最小数を見つける問題は広く研究されている。最もよく知られた例は,P_4とサイクルの二色コピーがそれぞれ許されないグラフ(Gr”unbaum,1973)の星彩色と非環状着色である。本論文では,これらの問題の変化を導入し,固定長の二色経路を含まないグラフの適切な彩色を研究し,非有向グラフGの全てのグラフに対する一般的限界を,GのP_kの二色コピーがないように,GのP_k色を,GのP_k-彩色化に必要な色の最小数,GのP_k-彩色数と呼ばれるGのP_k色数と呼ぶ,GのP_k-色数と呼ぶ,Gの適当な頂点彩色である,GのP_k-彩色性,および,GのP_k-着色に必要な最小色数,を,S_k(G)によって表示した。特に,全てのグラフに対するs_k(G)の限界を提供し,特に,最大次数d≧2,k≧4,s_k(G)=O(d ̄k-1/k-2)を持つ任意のグラフGに対して証明する。さらに,いくつかのサイクルの生成物のP_k色数およびk=5,6の経路に対する正確な値を見出した。【JST・京大機械翻訳】

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

グラフ理論基礎

, , ,

前のページに戻る