矛盾のない色指数に関するノート【JST・京大機械翻訳】

Kamyczura Mateusz; Meszka Mariusz; Przybylo Jakub

プレプリント

J-GLOBAL ID：202202213191262288 整理番号：22P0298690

矛盾のない色指数に関するノート【JST・京大機械翻訳】

A note on the conflict-free chromatic index

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

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

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

Gを最大度Δと分離頂点のないグラフとする。Gのエッジ彩色cは,あらゆるエッジの閉じた近傍が一意的に着色した要素を含むならば,無矛盾である。そのようなcを削除する最小色数は,χ’_CF(G)によって表示されるGの無矛盾色指数である。「コンフリクトフリー色数対コンフリクトフリー色指数」[J.グラフ理論,2022;99:349~358]では,χ’_CF(G)≦C_1log_2Δ+C_2,ここでC_1>337とC_2が定数である確率法により最近証明されたが,χ’_CF(G)≧(1-o(1))log_2Δを持つグラフのファミリーが存在する。このノートでは,χ’_CF(G)≦3log_2Δ+1,すなわちχ’_CF(G)≦3log_2χ(G)+1である,χ’_CF(G)≦3log_2Δ+1の明示的な簡単な証明を提供した。この目的のために,二部グラフに対するχ’_CF(G)≦4を暗示するいくつかの補助観測を証明した。【JST・京大機械翻訳】

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

グラフ理論基礎

, ,

前のページに戻る