クリティカルグラフ

グラフ理論において、臨界グラフとは、その真部分グラフの彩色数がより小さい無向グラフのことである。このようなグラフでは、すべての頂点または辺は、その削除によってグラフの彩色に必要な色の数が減るという意味で臨界要素である。臨界グラフから単一の辺または頂点（およびその接続辺）が削除されるたびに、そのグラフを彩色するために必要な色の数が 1 以上減少することはない。

-臨界グラフは、彩色数 を持つ臨界グラフです。彩色数 を持つグラフは、その各頂点が臨界要素である場合に-頂点臨界です。臨界グラフは、グラフ理論で非常に重要な尺度である彩色数に関して 最小のメンバーです。${\displaystyle k}$${\displaystyle k}$${\displaystyle G}$${\displaystyle k}$${\displaystyle k}$

頂点と辺を持つ-臨界グラフのいくつかの特性: ${\displaystyle k}$${\displaystyle G}$${\displaystyle n}$${\displaystyle m}$

• ${\displaystyle G}$コンポーネントは 1 つだけです。
• ${\displaystyle G}$は有限です (これはDe Bruijn-Erdős の定理です)。^[1]
• 最小次数は 不等式に従います。つまり、すべての頂点は少なくとも他の頂点と隣接しています。より強く、辺連結です。^[2]${\displaystyle \delta (G)}$${\displaystyle \delta (G)\geq k-1}$${\displaystyle k-1}$${\displaystyle G}$${\displaystyle (k-1)}$
• が次数 の正則グラフである場合、つまりすべての頂点が他の頂点と正確に隣接している場合、 は頂点を持つ完全グラフ、または奇数長の閉路グラフのいずれかです。これがブルックスの定理です。^[3]${\displaystyle G}$${\displaystyle k-1}$${\displaystyle k-1}$${\displaystyle G}$ ${\displaystyle K_{k}}$${\displaystyle n=k}$
• ${\displaystyle 2m\geq (k-1)n+k-3}$^[4 ]
• ${\displaystyle 2m\geq (k-1)n+\lfloor (k-3)/(k^{2}-3)\rfloor n}$^[5 ]
• どちらも2つの小さな臨界グラフに分解でき、各頂点ペア間の辺には2つのサブグラフのそれぞれから1つの頂点が含まれるか、少なくとも頂点があります。^[6]より強い言い方をすると、どちらもこのタイプの分解を持つか、またはのすべての頂点に対して、 がその色の唯一の頂点であり、他のすべての色クラスが少なくとも2つの頂点を持つ-彩色があります。 ^[7]${\displaystyle G}$${\displaystyle G}$${\displaystyle 2k-1}$${\displaystyle G}$${\displaystyle v}$${\displaystyle G}$${\displaystyle k}$${\displaystyle v}$

グラフが頂点臨界的であるためには、すべての頂点 に対して、が単独の色クラスとなる 最適な適切な彩色が存在する必要があります。${\displaystyle G}$${\displaystyle v}$${\displaystyle v}$

Hajós (1961) が示したように、あらゆる-臨界グラフは、Hajós 構成と 2 つの隣接しない頂点を識別する操作を組み合わせることで、完全グラフから形成できます。この方法で形成されたグラフには、適切な色付けでは常に色が必要です。^[8]${\displaystyle k}$ ${\displaystyle K_{k}}$${\displaystyle k}$

二重臨界グラフは、隣接する頂点のペアを削除すると彩色が2減少する連結グラフです。が唯一の二重臨界-彩色グラフであるかどうかを判断することは未解決の問題です。^[9]${\displaystyle K_{k}}$${\displaystyle k}$

• 因子臨界グラフ

ウィキメディア・コモンズには、クリティカルグラフに関連するメディアがあります。