バランス可能な単純バランス可能な正規グラフについて

私たちは、Caro、Hansberg、Montejanoによって2021年に定義されたバランス可能なグラフの研究を続けます。これは、グラフGが十分に多くの色のエッジを含む十分に大きな完全グラフのエッジに対する任意の2色付けがGのバランスの取れたコピーを含むグラフです。バランス可能なグラフの認識問題は、Dailly、Hansberg、Venturaによって2021年にNP完全であると推測されましたが、バランス可能なグラフは優雅な組合せ的特徴を持ちます。すなわち、あるグラフがバランス可能であるためには、すべてのエッジの半分を含む頂点部分集合と、対応するカットがすべてのエッジの半分を含むようなもう一つの部分集合が存在する必要があります。この性質の特別なケース、すなわち二つの集合の一つが頂点被覆である場合を考慮し、対応するグラフを単純バランス可能と呼びます。バランス可能および単純バランス可能な正規グラフに関するいくつかの結果を証明します。まず、グラフの独立数に関わる条件を通じて単純バランス可能な正規グラフを特徴付けます。次に、2021年のDailly、Hansberg、Venturaの質問に取り組み、すべての立方体グラフがバランス可能であることを示します。第三に、ブルックスの定理を用いて、順序が4で割り切れるすべての4-正規グラフがバランス可能であることを示します。最後に、9-正規グラフが単純バランス可能であるかどうかを決定することがNP完全であることを示します。