その他の属性

ウィキペディア小見出し辞書

その他の属性

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/28 15:48 UTC 版)

「グラフ彩色」の記事における「その他の属性」の解説

平面グラフでは、頂点彩色は基本的に nowhere-zero flow と双対関係にある。 無限グラフについては、まだよく判っていない。無限グラフの彩色について判明している数少ない事実として次の事柄がある。 無限グラフ G の全ての有限部分グラフが k-彩色可能であれば、選択公理を仮定した場合にG自体も同様である(de Bruijn & Erdős 1951)。 また、n ≥ n0 の n 色全部を使って彩色可能なグラフは、無限完全彩色可能である(Fawcett 1978)。