ハイパーグラフ2色性へのグラフの色数の削減

私は、GareyとJohnsonのComputers and IntractabilityでSet Splitting
Problemについて言及されているLovasz
1973の「ハイパーグラフの被覆と着色」と題したこの論文に従っています。本論文では、著者がグラフの色数をハイパーグラフ2色性(set
splittingと同じ)に減らそうとしている。

You can find the paper here: http://web.cs.elte.hu/~lovasz/old-papers.html

私は以下の削減を再現しています。

$ G $をグラフとすると、$ V(G)= {x_1、 dots、x_n } $となる。 $ G_i $を$ G
$、$(i = 1、 dots、k)$、$ V(G_i)= {x_ {i、1}、 dots、x_ {i、n} } $($
x_ {iv} $は$ x_v $に対応する点です)。新しい点$ y $をとり、$ f_v = {x_ {1、v}、
dots、x_ {k、v}、y } $とする。ハイパーグラフ$ H $を $$   H = E(G_1)
cup dots cup E(G_k) cup {f_1、 dots、f_n } $$ $ H $は$ G
$が$ k $ -colorableの場合にのみ2色で表示されます。
この結論は理解できません。これは$ k = 1
$です。

ベストアンサー

もう1つの答えが指摘しているように、元の論文の縮小にはバグがあるようです:$ G $が二者でなければ、$ H
$は二色にならないでしょう。私は他の回答の仕事の減少を証明する方法をかなり見ることができませんでしたが、ここでは私が考えているものがあります。

$ H $の頂点はV(G)} cup {z } $の$ {x_ {i、v}:i [v]]になります。 $ H
$はV(G)$のすべての$ v に対してエッジ$ f_v = {x_ {1、v}、 ldots、x_ {k、v} }
$を持ち、 E(G)$、および各$ i [k] $の辺$ {z、x_ {i、u}、x_ {i、v} }
$に含まれる。

$ G $の色付け$ chi_G:V(G)に[$ k $]を与えると、$ H $の {0,1 }
$へのV(H)設定で$

$$ chi_H(z)= 1、\ chi_H(x_ {i、v})= 1 iff chi_G(v)= iである。
$$

$ H $のエッジが単色でないことを確認するのは簡単です。

他の方向では、$ chi_H $を$ H $の適切な2色とし、$ chi_H(z)= 1 $とする。
(もし色の名前を変更するだけではないならば)。エッジ$ f_v $は単色ではないので、V(G)$の全ての$ v に対して$
chi_H(x_ {i、v })= 1 $。そのような$ i $を選び、$ chi_G(v)= i
$を設定する。これは適切な色づけである、そうでなければ、$ chi_H(x_ {i、u})= $ H($、$)$ = $ $ $
{$、$ {$} $ {i、v}

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です