查看“︁色临界图”︁的源代码

{{Multiple issues|
{{Expand language|1=en|time=2021-12-24T23:57:25+00:00}}
{{Onesource|time=2021-12-24T23:57:25+00:00}}
}}
數學分支[[圖論]]中，'''色临界图'''或'''臨界圖'''（{{lang-en|critical graph}}）是[[图染色问题]]中一类特殊的[[圖 (數學)|圖]]，從此類圖中，移除任何一邊或一點，皆會使圖的[[色數]]減少。这一类图具有一些非常好的性质，能在很多证明定理中发挥用处。

== 定义 ==
如果图<math>G</math>的任意一个真[[子图]]<math>G'\subset G</math>，其[[色數]]均满足<math>\chi(G')<\chi(G)</math>，则称<math>G</math>为<math>\chi(G)</math>色临界图（{{lang-en|<math>\chi(G)</math>-critical graph}}）。<ref name = "west">{{cite book |author1=Douglas B.West |title=Introduction to Graph Theory |publisher=Pearson Enducation |isbn=81-7808-830-4 |pages=210-220}}</ref>

== 相关定义 ==

=== 图染色数 ===
{{also|圖染色問題}}
对于给定的图<math>G</math>，存在<math>k</math>种颜色和一种染色方案，将图中<math>G</math>每一个顶点都染成<math>k</math>种颜色中的一种。如果染色方案满足一下条件，那么将称该染色方案为恰当的染色方案：对于图<math>G</math>中任意两个顶点<math>u,v</math>，如果<math>uv\in E(G)</math>，那么<math>u,v</math>所染成的颜色不同。

对于图<math>G</math>，如果存在一个<math>k</math>种颜色的恰当染色方案，我们称<math>G</math>是<math>k</math>染色的。在所有满足条件的<math>k\in \mathbb{Z_+}</math>，称最小的那个<math>k</math>为<math>\chi(G)</math>。

=== 子图 ===
对于任意一个图<math>G</math>和<math>G'</math>，如果<math>V(G')\subseteq V(G)
</math>并且<math>E(G')\subseteq E(G)</math>，则称<math>G'</math>是<math>G</math>的子图，记为<math>G'\subseteq G</math>。若<math>G'\neq G</math>，则称<math>G'</math>是<math>G</math>的真子图，记为<math>G'\subset G</math>。

=== 叶（lobe） ===
对于图<math>G</math>即其一个点的子集<math>S\subseteq V(G)</math>。<math>G-S</math>有连通分支<math>G_1,G_2\dots G_t</math>。对任意<math>G_i</math>，我们称<math>S\cup G_i</math>在<math>G</math>中的[[导出子图]]为<math>S</math>-叶（<math>S</math>-lobe）。

== 基本性质 ==
#<math>G</math>是一个没有孤立点的色临界图，當且僅當對任意<math>e\in E(G),\ \chi(G-e)<\chi(G)</math>。
#:证明："<math>\Rightarrow </math>"由定义可知显然。"<math>\Leftarrow</math>"：由于<math>\forall G'\subset G, \exists e\in G-G'</math>。所以<math>\chi(G')\le \chi(G-e)<\chi(G)</math>。
#设G是一个<math>k</math>-色临界图，则對任意<math>v\in V(G)</math>，存在一种使用<math>k</math>种颜色的恰当的染色方式使得<math>k-1</math>种颜色均出现在{{le|鄰域 (圖論)|Neighbourhood (graph theory)|鄰域}}<math>N(v)</math>中。
#:证明：由于色临界图的定义知，<math>\chi(G-v)<k</math>。所以存在一种使用前<math>k-1</math>种颜色对<math>G-v</math>的恰当的染色方式。然后再对<math>v</math>进行染色，则必须有<math>k-1</math>种颜色均出现在<math>N(v)</math>中，否则可以用前<math>k-1</math>種色中没有在出现<math>N(v)</math>的颜色对<math>v</math>染色，那么就得到用前<math>k-1</math>颜色对<math>G</math>染色的方法，与<math>\chi(G)=k</math>矛盾。
#设G是一个<math>k</math>-色临界图，则对任意<math>e\in E(G)</math>，任意使用<math>k-1</math>种颜色对<math>G-e</math>的恰当的染色方式均将<math>e</math>两端点染成相同颜色。
#:证明：如果存在一种使用<math>k-1</math>种颜色对<math>G-e</math>的恰当的染色方式使得<math>e</math>两端点染成不同颜色，那么这种方式同样能对<math>G</math>使用，这样与<math>\chi(G)=k</math>矛盾。

== 相关定理 ==

=== 狄拉克定理===
任意一个<math>k</math>-色临界图均为<math>k-1</math>-{{le|k邊連通圖|k-edge-connected graph|邊連通}}的。<ref name = "west"/>{{rp|211}}

证明用到以下引理：

==== 凯南（{{lang|en|Kainen}}）引理 ====
设<math>G</math>的最小染色数<math>\chi(G)>k</math>，并且<math>X, Y</math>是对<math>V(G)</math>的一个[[集合劃分|划分]]。如果<math>X, Y</math>在<math>G</math>上[[导出子图]]<math>G[X],G[Y]</math>均是<math>k</math>可染色的，那么<math>G-G[X]-G[Y]</math>中至少有<math>k</math>条边。<ref name = "west"/>{{rp|211}}

证明：

由于<math>G[X], G[Y]</math>均是<math>k</math>可染色的，可以把<math>X</math>划分为<math>k</math>个独立集<math>X_1, X_2,\dots, X_k</math>，把<math>Y</math>划分为<math>k</math>个[[独立集]]<math>Y_1, Y_2, \dots,  Y_k</math>。如果<math>X,Y</math>之间边少于<math>k</math>条，則对<math>G</math>进行染色。先对<math>X_1,X_2, \dots, X_k</math>中的点染上<math>k</math>种颜色。再分别对<math>Y_1,Y_2, \dots,  Y_k</math>逐独立集染色，并且染每个独立集时，与其相邻以及染完色的独立集个数少于<math>k</math>个，所以可在<math>k</math>中颜色中选择餘下某种对其恰当染色。这样就对<math>G</math>使用<math>k</math>种颜色恰当染色，与<math>\chi(G)>k</math>矛盾。引理证明完毕。

回到原证明，如果<math>G</math>不是<math>k-1</math>-边连通的。那么存在<math>k-2</math>条边<math>E'=\{e_1,e_2\dots e_{k-1}\}</math>使得<math>G-E'</math>不是连通图，取其一个连通分支<math>X</math>，令<math>Y=V(G)-X</math>。由于不连通性可知<math>G-G[X]-G[Y]</math>的邊皆屬<math> E'</math>。又<math>G</math>是色临界图，有<math>\chi(G[X])<k,\chi(G[Y])<k</math>，所以均是<math>k-1</math>可染色。利用凯南引理可知，<math>G-G[X]-G[Y]</math>的邊數至多是<math> k-1</math>，但<math>|E'|=k-2</math>，矛盾。

=== 定理2： ===
如果<math>G</math>是<math>k</math>-色临界图，那么<math>G</math>的{{le|割集|Cut (graph theory)}}均不是[[團 (圖論)|團]]。特别说明的是，如果<math>G</math>有一个割集含有两个点<math>S=\{x,y\}</math>，那么<math>xy\notin G</math>并且<math>G</math>存在一个<math>S
</math>-叶<math>H</math>使得<math>\chi(H+xy)=k</math>。<ref name = "west"/>
==参考内容==
{{reflist}}

[[Category:图族]]
[[Category:图染色]]