弦グラフの適切な配向数について【JST・京大機械翻訳】

Araujo Julio; Cezar Alexandre; Lima Carlos V. G. C.; Santos Vinicius F. dos; Silva Ana

プレプリント

J-GLOBAL ID：202202201779880290 整理番号：22P0213615

弦グラフの適切な配向数について【JST・京大機械翻訳】

On the proper orientation number of chordal graphs

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

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

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

グラフG=(V,E)の配向Dは,同じエンド頂点を持つ二つの可能なアークの1つによって各エッジを置き換えることによりGから得られたダイグラフである。d ̄-_D(v)によって表示されたDにおけるvの次数は,Dにおける頭部vを有するアークの数である。Gの配向Dは,d ̄-_D(u)≠d ̄-_D(v)がすべてのuv>E(G)に対して適切である。ほとんどのkで最大値を持つ方位はk方位と呼ばれる。χ(G)によって表示されたGの適切な配向数は,Gが適当なk方向を許すような最小整数kである。χ(G)≦kが有界直径の弦グラフに対してNP完全であるかどうかを決定するが,準閾値グラフのサブクラスにおいて線形時間で解くことができる。kによってパラメータ化するとき,著者らは,この問題が弦グラフのためのFPTであると主張して,多項式カーネルが存在しないことを主張した。分割グラフのサブクラスとコビパートグラフのクラスに対する線形カーネルに対するより良いカーネルを示した。限界に関しては,ブロックグラフのサブクラスに対するタイトな上限を証明した。また,著者らは,ほとんどの2およびほとんどの3で適切な配向数を有する樹木の新しいファミリーを提示した。実際に,著者らは,少なくともc+1程度の隣接頂点を持たないグラフGが,ほとんどのcで適切な配向数を持つという一般的結合スタチンを証明した。これは,有界固有配向数を有する新しいクラスの(外部)平面グラフを意味する。また,弱い二重が経路である最大外部平面グラフGは,χ(G)≦13を満たすことを証明した。最後に,著者らは,弦の爪のないグラフとグラフのクラスに対する単純な限界を示した。【JST・京大機械翻訳】

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

集合論 , グラフ理論基礎

, ,

前のページに戻る