スパースグラフと平面グラフの奇数彩色【JST・京大機械翻訳】

Cho Eun-Kyung; Choi Ilkyoo; Kwon Hyemin; Park Boram

プレプリント

J-GLOBAL ID：202202219327614971 整理番号：22P0293879

スパースグラフと平面グラフの奇数彩色【JST・京大機械翻訳】

Odd coloring of sparse graphs and planar graphs

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

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

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

グラフの{odd c-coloring}は,各非分離頂点が,その近傍に奇数の時間を示す色を持つような適切なc-彩色である。この概念は,Petru v sevskiとv Skrekovskiにより最近導入され,かなりの注目を集めている。Cranstonは,有界最大平均度を有するグラフの奇数彩色を研究し,mad(G)≦4c-4/c+1を有するあらゆるグラフGがc≧4に対して奇数c-彩色を持ち,c≡5,6}の予想を証明した。特に,少なくとも7および6のgirthを有する平面グラフは,それぞれ奇数5色および奇数6色を有した。Cranstonの予想を完全に解決した。c≧7では,Cranstonにより暗黙的に示唆されたが,c=4では,予想が真であり,c=4では,全てが5サイクルを含む反例を構築することを示した。一方,mad(G)<22/9のグラフGと誘起された5サイクルは奇数の4色を持たないことを示した。これは,少なくとも11のgirthを持つ平面グラフが奇数4色を持つことを意味する。また,少なくとも5のgirthを持つ平面グラフは奇数の6色を持つことを証明した。【JST・京大機械翻訳】

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

グラフ理論基礎

, ,

前のページに戻る