完美图定理

在图论中，完美图定理（由洛瓦兹·拉兹洛证明László Lovász （1972a, 1972b））断言：一个无向图是完美的当且仅当其补图也是完美的。这个结论一度是Claude Berge（英语：Claude Berge）提出的猜想。它有时也被称为弱完美图定理，以和强完美图定理[1]作区分。强完美图定理通过禁止导出子图来刻画完美图。

定理叙述

一个完美图是具有下述性质的无向图：在其每个导出子图中，最大团的顶点数都等于对该导出子图的着色的颜色数的最小值。完美图包括了很多重要类型的图，例如二分图、弦图和可比图（英语：comparability graph）。

一个图的补图在某两个顶点之间连一条边当且仅当原图在这两个顶点之间没有连边。从而原图中的团成为其补图中的独立集，而原图的一个染色成为其补图的一个团覆盖。

完美图定理断言：完美图的补图也是完美的。

等价地，在完美图中，最大独立集的顶点数等于其团覆盖中团个数的最小值。

例子

 
一个有7个顶点的圈和它的补图，有7个顶点的反洞。在两个图中都标出了最小染色和最大团（用黑色加粗标注）。因为两个图的染色数都不等于其最大团的顶点数，所以它们都不是完美的。

令G是一个长度为大于3的奇数的循环图（洞），则G的任何染色需要至少3种颜色，但G不含有三角形，所以它不是完美的。由完美图定理，G的补图（一个奇数长度的反洞）肯定也不是完美的。如果G是一个长度为5的圈，则它是一个自补图（英语：Self-complementary graph），但此性质对更大的奇数长度不再成立，而对于奇数个顶点的反洞计算其团数和色数也不像对于奇数个顶点的循环图那么容易。强完美图定理指出，奇数长度的洞和反洞是完美图的最小的禁止导出子图。

应用

在一个非平凡的二分图中，由定义染色所需的颜色数最小是2，而由于二分图中不含有三角形，其团数也是2。而二分图的任何导出子图还是二分图。所以二分图是完美的。在有n个顶点的二分图中，一个最小团覆盖需要一个最大匹配加上另一些团，每个对应于一个未匹配顶点，其中团的个数等于n-M，这里M是最大匹配的边数。于是在这个例子中完美图定理可以推出柯尼希定理 (图论)，即有n个顶点的二分图的最大独立集的顶点数也是n-M[2]

洛瓦兹的证明

和强完美图定理的关系

Chudnovsky 等人 (2006)得到的强完美图定理断言一个图是完美的当且仅当其所有导出子图和它们的补图都不是长度为大于等于5的奇数的循环图。由于此条件在取补图后不变，强完美图定理可以直接推出（弱）完美图定理。

推广

Cameron，Edmonds & Lovász (1986)证明，如果一个完全图的所有边被分成三个导出子图，使得任何三个顶点都在其中一个导出子图中连通，且两个导出子图是完美的，则第三个导出子图必然也是完美的。完美图定理是这个结果在其中一个导出子图是空图时的特例。

注释

  1. ^ 强完美图定理也是Claude Berge的猜想之一，但在多年之后的2006年才被Chudnovsky-Robertson-Seymour-ThomasChudnovsky 等人 (2006)证明。
  2. ^ Kőnig (1931), 后来被Gallai (1958)重新得到。

参考文献

  • Berge, Claude, Färbung von Graphen, deren sämtliche beziehungsweise deren ungerade Kreise starr sind, Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg, Mathematisch-naturwissenschaftliche Reihe, 1961, 10: 114 （德语） .
  • Berge, Claude, Perfect graphs, Six Papers on Graph Theory, Calcutta: Indian Statistical Institute: 1–21, 1963 .
  • Cameron, K.; Edmonds, J.; Lovász, L., A note on perfect graphs, Periodica Mathematica Hungarica, 1986, 17 (3): 173–175, MR 0859346, doi:10.1007/BF01848646 .
  • Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin, The strong perfect graph theorem, Annals of Mathematics, 2006, 164 (1): 51–229, MR 2233847, arXiv:math/0212070  , doi:10.4007/annals.2006.164.51 .
  • Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin, Progress on perfect graphs (PDF), Mathematical Programming, Series B., 2003, 97 (1-2): 405–422 [2020-05-03], MR 2004404, doi:10.1007/s10107-003-0449-8, （原始内容存档 (PDF)于2010-07-31） .
  • Gallai, Tibor, Maximum-minimum Sätze über Graphen, Acta Mathematica Academiae Scientiarum Hungaricae, 1958, 9 (3-4): 395–434, MR 0124238, doi:10.1007/BF02020271 （德语） 
  • Golumbic, Martin Charles, 3.2. The perfect graph theorem, Algorithmic Graph Theory and Perfect Graphs, New York: Academic Press: 53–58, 1980, ISBN 0-12-289260-7, MR 0562306 .
  • Kőnig, Dénes, Gráfok és mátrixok, Matematikai és Fizikai Lapok, 1931, 38: 116–119 （匈牙利语） 
  • Lovász, László, Normal hypergraphs and the perfect graph conjecture, Discrete Mathematics, 1972a, 2 (3): 253–267, doi:10.1016/0012-365X(72)90006-4 .
  • Lovász, László, A characterization of perfect graphs, Journal of Combinatorial Theory, Series B, 1972b, 13 (2): 95–98, doi:10.1016/0095-8956(72)90045-7 .
  • Reed, Bruce A., From conjecture to theorem, Ramírez Alfonsín, Jorge L.; Reed, Bruce A. (编), Perfect Graphs, Wiley-Interscience Series on Discrete Mathematics and Optimization, Chichester: Wiley: 13–24, 2001, MR 1861356 .