マセマティカ エテルナ
オープンアクセス

概要

ショートコミュニケーションガライグラフとアンチガライグラフ

モハメド・フセイン

グラフ G のガライ グラフと反ガライ グラフは、G の周囲を頂点とします。G の 2 つの辺は、G のガライ グラフ内で隣接しているが G 内の三角形をまたいでいない場合、隣接しています。また、G の反ガライ グラフ内で隣接している場合、それらは G 内の三角形をまたいでいます。この論文では、次のことを示します。4 色定理は反ガライ グラフに関しても同義です。ガライ グラフの内円範囲、つまり彩色範囲の問題は NP 完全です。さらに、ガライ グラフと理想グラフの理論との関係について説明します。ガライ グラフと反ガライ グラフの特徴付けも [1] で示されています。