완벽한 그래프 정리

Perfect graph theorem

그래프 이론에서, Laszlo Lovasz(1972a, 1972b)의 완벽한 그래프 정리에서는, 비방향 그래프는 그것의 보완 그래프 또한 완벽해야 완벽하다고 말한다.이 결과는 베르헤(1961년, 1963년)에 의해 추측되어 왔으며, 때로는 그들의 금지된 유도 서브그래프에 의해 완벽한 그래프를 특징짓는 강한 완벽 그래프 정리와[1] 구별하기 위해 약한 완벽 그래프 정리라고 불리기도 한다.

성명서

완벽한 그래프는 유도된 서브그래프 하나에서 가장 큰 클릭의 크기가 서브그래프의 색상의 최소 색 수와 같다는 특성을 가진 비방향 그래프다.완벽한 그래프에는 초당적 그래프, 화음 그래프, 비교가능성 그래프를 포함한 많은 중요한 그래프 클래스가 포함된다.

그래프의 보완점은 원래 그래프가 동일한 두 꼭지점 사이에 가장자리가 없는 경우에만 두 꼭지점 사이에 가장자리가 있다.따라서 원본 그래프의 클릭은 보완에서 독립된 집합이 되고 원본 그래프의 색상은 보완의 클릭 커버가 된다.

완벽한 그래프 정리에는 다음과 같은 내용이 나온다.

완벽한 그래프의 보완이 완벽하다.

동등하게, 완벽한 그래프에서, 최대 독립 집합의 크기는 clique cover의 최소 clique 수와 같다.

예

7-Vertex 사이클과 그 보완물인 7-Vertex 안티홀은 각각의 경우에서 최적의 색상과 최대 클라이크(가장자리가 무겁다)를 보여준다.어느 그래프도 그것의 클라이크 크기와 동일한 수의 색상을 사용하므로, 어느 그래프도 완벽하지 않다.

G를 3보다 큰 홀수 길이의 사이클 그래프( 이른바 "이상한 구멍")로 한다.그러면 G는 어떤 색에도 적어도 3가지 색상이 필요하지만 삼각형이 없기 때문에 완벽하지 않다.따라서 완벽한 그래프 정리에 의해 G(이상한 안티홀)의 보완도 완벽하지 않아야 한다.G가 5정점 주기의 주기라면 그 보완점에 이형이지만, 이 특성은 더 긴 홀수 주기에 대해서는 사실이 아니며, 홀수 구멍에 있는 것처럼 홀수 안티홀에 있는 클리크 숫자와 색수를 계산하는 것도 하찮지 않다.강력한 완벽한 그래프 정리가 말해주듯 홀수 구멍과 홀수 안티홀은 완벽한 그래프를 위한 최소한의 금지 유도 서브그래프로 판명된다.

적용들

초당적 그래프 이외의 그래프에서 색의 최적 개수는 (정의에 따라) 2이고, (이중적 그래프는 삼각형이 없기 때문에) 최대 클라이크 크기 또한 2이다.또한, 초당적 그래프의 유도 하위 그래프는 초당적 그래프로 남아 있다.따라서 초당적 그래프는 완벽하다.n-vertex 초당적 그래프에서 최소 클라이크 커버는 매칭의 카디널리티인 n - M 크기로 매칭되지 않은 모든 정점에 대한 추가 클라이크와 함께 최대 일치의 형태를 취한다.따라서 이 경우 완벽한 그래프 정리는 초당적 그래프에 있는 최대 독립 집합의 크기 또한 n - M이라는 Kőnig의 정리를 내포하고 있는데,[2] 이는 베르헤가 완벽한 그래프 이론을 공식화한 데 주요한 영감을 준 결과였다.

칸막이로 분할된 세트의 높이를 반창고로 특징짓는 미르스키의 정리는 부분적으로 정렬된 세트의 비교가능성 그래프의 완성도로서, 칸막이로 된 세트의 폭을 체인으로 구분하는 딜워스의 정리는 그 완벽함으로 공식화될 수 있다.이 그래프의 보완따라서 완벽한 그래프 정리는 미르스키의 정리에 대한 (거의 더 쉬운) 증거로부터 딜워스의 정리를 증명하는 데 사용될 수도 있고, 그 반대도 마찬가지일 수도 있다.[3]

로바스의 증거

완벽한 그래프 정리를 증명하기 위해, 로바스츠는 그래프에서 정점을 패크로 교체하는 작업을 사용했다; 만약 그래프가 완벽하다면, 이 교체 과정에 의해 형성된 그래프도 완벽하다는 것은 이미 베르게에게 알려져 있었다.[4]이러한 모든 교체 과정은 정점을 두 배로 늘리는 반복적인 단계로 세분될 수 있다.이중 꼭지점이 그래프의 최대 클릭에 속할 경우 클릭 수와 색도 수를 모두 1씩 증가시킨다.반면에, 두 개의 정점이 최대 정점에 속하지 않는 경우, 주어진 그래프의 최적 색상에서 두 개의 정점(두 개의 정점 자체는 아님)과 같은 색상의 정점을 제거하여 그래프 H를 형성한다.제거된 정점들은 모든 최대 집단을 충족하기 때문에 H는 주어진 그래프보다 1이 적은 정점수와 색수를 가진다.제거된 정점과 이중 정점의 새 복사본은 단일 색상 등급으로 다시 추가될 수 있으며, 이 경우 이중화 단계가 색수를 변경하지 않음을 보여준다.같은 주장은 복제가 주어진 그래프의 모든 유도 하위그래프에서 클라이크 수와 색수의 동일성을 보존한다는 것을 보여주므로, 각 복제가 이루어질 때마다 그래프의 완전성이 유지된다.[5]

완벽한 그래프 G가 주어진 경우, Lovász는 각 꼭지점 v를 tv 정점의 한 종류로 교체하여 그래프 G*를 형성한다. 여기서v t는 v를 포함하는 G에서 구별되는 최대 독립 집합의 수입니다.G*에서 선택한 최대 독립 집합이 모두 분리되고 선택된 단일 집합에 G*의 각 정점이 나타나는 방식으로 G*의 각 개별 최대 독립 집합과 G*의 최대 독립 집합에 대응하는 것이 가능하다. 즉, G*는 각 색상 등급이 최대 독립 집합인 색상을 가지고 있다.반드시 이 색상은 G*의 최적색이다.G가 완벽하기 때문에 G*도 완벽하기 때문에 이 색상의 색의 수와 같은 크기를 가진 최대 클릭 K*가 있으며, 이는 G에서 구별되는 최대 독립 집합의 수입니다. K*는 이러한 최대 독립 집합 각각에 대한 뚜렷한 대표성을 포함해야 한다.G에서 정점의 해당 집합 K(G*의 확장된 부류가 K*를 교차하는 정점)는 G의 모든 최대 독립 집합과 교차하는 특성을 가진 G의 집단이다.따라서 K를 제거하여 G에서 형성된 그래프는 G의 클릭 수보다 1개 적은 클릭 커버 번호와 G의 독립 수보다 1개 적은 독립 번호를 가지며, 그 결과는 이 숫자에 대한 유도에 따른다.[6]

강인한 완벽한 그래프 정리와의 관계

추드노브스키 외 연구진의 강력한 완벽한 그래프 정리. (2006)은 유도 서브그래프 중 어느 것도 5보다 크거나 같은 홀수의 주기 또는 그 보완인 경우에만 그래프가 완벽하다고 명시한다.이러한 특성화는 그래프 보완의 영향을 받지 않기 때문에, 그것은 즉시 약한 완벽한 그래프 정리를 암시한다.

일반화

카메론, 에드먼즈 & 로바스즈(1986)는 세 개의 정점마다 세 개의 서브그래프 중 하나에 연결된 그래프를 유도하는 방식으로 전체 그래프의 가장자리를 세 개의 서브그래프로 분할하고, 서브그래프 중 두 개가 완벽하다면 세 번째 서브그래프도 완벽하다는 것을 증명했다.완벽한 그래프 정리는 세 개의 서브그래프 중 하나가 빈 그래프일 때 이 결과의 특별한 경우다.

메모들

  1. ^ 이것은 베르헤에 의해서도 추측되었지만 훨씬 후에야 추드노브스키 외 에 의해 증명되었다. (2006).
  2. ^ Kőnig(1931년), 후에 갈라이(1958)에 의해 재발견되었다.
  3. ^ 골룸빅(1980), 섹션 5.7, "비교성 그래프의 색상 및 기타 문제", 페이지 132–135.
  4. ^ 골룸빅(1980), 리마 3.1(i) 및 리드(2001) 코롤라리 2.21을 참조한다.
  5. ^ 리드(2001), 리마 2.20.
  6. ^ 우리는 여기에서 리드(2001)의 증거에 대한 설명을 따른다.골룸빅(1980)은 이러한 추리의 상당 부분이 D에 의해 빠르게 재구성되었다고 지적한다. R. 풀커슨은 로바스츠의 결과를 듣고도 그의 증거를 보지 못했다.

참조

  • Berge, Claude (1961), "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 (in German), 10: 114.
  • Berge, Claude (1963), "Perfect graphs", Six Papers on Graph Theory, Calcutta: Indian Statistical Institute, pp. 1–21.
  • Cameron, K.; Edmonds, J.; Lovász, L. (1986), "A note on perfect graphs", Periodica Mathematica Hungarica, 17 (3): 173–175, doi:10.1007/BF01848646, MR 0859346.
  • Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics, 164 (1): 51–229, arXiv:math/0212070, doi:10.4007/annals.2006.164.51, MR 2233847.
  • Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2003), "Progress on perfect graphs" (PDF), Mathematical Programming, Series B., 97 (1–2): 405–422, doi:10.1007/s10107-003-0449-8, MR 2004404.
  • Gallai, Tibor (1958), "Maximum-minimum Sätze über Graphen", Acta Mathematica Academiae Scientiarum Hungaricae (in German), 9 (3–4): 395–434, doi:10.1007/BF02020271, MR 0124238
  • Golumbic, Martin Charles (1980), "3.2. The perfect graph theorem", Algorithmic Graph Theory and Perfect Graphs, New York: Academic Press, pp. 53–58, ISBN 0-12-289260-7, MR 0562306.
  • Kőnig, Dénes (1931), "Gráfok és mátrixok", Matematikai és Fizikai Lapok (in Hungarian), 38: 116–119
  • Lovász, László (1972a), "Normal hypergraphs and the perfect graph conjecture", Discrete Mathematics, 2 (3): 253–267, doi:10.1016/0012-365X(72)90006-4.
  • Lovász, László (1972b), "A characterization of perfect graphs", Journal of Combinatorial Theory, Series B, 13 (2): 95–98, doi:10.1016/0095-8956(72)90045-7.
  • Reed, Bruce A. (2001), "From conjecture to theorem", in Ramírez Alfonsín, Jorge L.; Reed, Bruce A. (eds.), Perfect Graphs, Wiley-Interscience Series on Discrete Mathematics and Optimization, Chichester: Wiley, pp. 13–24, MR 1861356.