数学 › グラフ理論 › 彩色

三角形分割のリスト彩色(Thomassen)

補題 7.2(「彩色」§7) ・ ✓公理まで証明済み

GG を外周 C=v1v2⋯vpv1C=v_1v_2\cdots v_pv_1 の三角形分割とする。相異なる色 c1,c2c_1,c_2 と、v1,v2v_1,v_2 以外の頂点のリスト L(v)L(v) が与えられ、

  • CC の上の頂点 v≠v1,v2v\ne v_1,v_2 では ∣L(v)∣≥3|L(v)|\ge3、
  • CC の上にない頂点 vv では ∣L(v)∣≥5|L(v)|\ge5

であるとする。このとき、c(v1)=c1c(v_1)=c_1、c(v2)=c2c(v_2)=c_2 で、他の頂点では c(v)∈L(v)c(v)\in L(v) となる GG の彩色 cc が存在する。

本文で読む(証明と前後の説明)→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を 前提 としてたどると、Rikai の中の証明だけで定義・公理(物理では基本仮定)までつながっています(前提の定理類 55 件、定義なども含めて 63 件)。

印の意味: ✓公理まで証明済み ・ △証明あり(閉包未完)・ ※主張のみ。テーマごとの集計は 閉包の状況。

前提をたどる 証明が使う定理・定義(直接 6 件)

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

これを使っている定理 証明で参照している 1 件