강력한 완벽한 그래프 정리

Strong perfect graph theorem

그래프 이론에서, 강력한 완벽한 그래프 정리는 완벽한 그래프를 홀수 홀수(이상한 길이 유도 사이클)와 홀수 안티홀(이상한 구멍의 합성)이 없는 그래프로서, 정확하게는 완벽한 그래프의 금지된 그래프 특성화다.1961년 클로드 버지에 의해 추측되었다.마리아 추드노브스키, 닐 로버트슨, 폴 시모어, 로빈 토마스의 증빙서가 2002년에[1] 발표되었고 2006년에 이들에 의해 출판되었다.

이 강력한 완벽한 그래프 정리의 증거는 카네기 멜론 대학의[2] 제라드 코르누에졸스가 제공한 1만 달러의 상금과 2009년 풀커슨 상을 수상하였다.[3]

성명서

완벽한 그래프는 모든 유도 하위 그래프에 대해 최대 클라이크의 크기가 그래프의 색상의 색상의 최소 개수와 같은 그래프를 의미한다. 완벽한 그래프는 초당적 그래프, 화음 그래프, 비교가능성 그래프를 포함하여 잘 알려진 그래프 클래스를 포함한다.1961년과 1963년에 처음으로 이 등급의 그래프를 정의하는 그의 작품에서, 클로드 버지는 홀수 구멍이 2번과 3번 색도를 가지고 있기 때문에 5번 이상의 길이의 홀수 길이 사이클 그래프의 형태로 유도된 하위 그래프를 포함하는 것은 완벽한 그래프가 불가능하다고 보았다.마찬가지로, 그는 완벽한 그래프는 홀수 구멍을 보완하는 유도 하위 그래프를 포함할 수 없다고 보았다: 2k + 1 정점을 가진 홀수 안티홀은 clique number k와 색도 number k + 1을 가지고 있는데, 이것은 완벽한 그래프에서는 다시 불가능하다.홀수 구멍도, 홀수 안티홀도 없는 그래프는 버지 그래프로 알려지게 되었다.

Berge는 모든 Berge 그래프가 완벽하거나, 완벽한 그래프와 Berge 그래프가 동일한 종류의 그래프를 정의한다고 추측했다.이것은 강력한 완벽한 그래프 추측으로 알려지게 되었고, 2002년에 그것이 강한 완벽한 그래프 정리라고 이름이 바뀌기 전까지 증명되었다.

약한 완전 그래프 정리와의 관계

1972년 Laszlo Lovász에 의해 증명된 Berge의 또 다른 추측은 모든 완벽한 그래프의 보완도 완벽하다는 것이다.이것은 완벽한 그래프 정리, 또는 (강력한 완벽한 그래프 추측/테오렘과 구별하기 위해) 약한 완벽한 그래프 정리라고 알려지게 되었다.버지의 금지된 그래프 특성화는 자기 보완적이기 때문에, 약한 완벽 그래프 정리는 강한 완벽 그래프 정리에서 바로 뒤따른다.

증명 아이디어

추드노브스키 외 연구진에 의한 강력한 완벽한 그래프 정리의 증거는 콘포르티, 코르누에졸스, 로버슨, 세이모어, 토마스에 의해 2001년에 추측된 개요를 따르며, 이에 따르면 모든 베르게 그래프는 5가지 유형의 기본 구성 블록(완벽한 그래프의 특수 등급) 중 하나를 이루거나 4가지 구조 분해의 다른 유형 중 하나를 가진다.간단한 그래프로 나누다최소한의 불완전한 Berge 그래프는 이러한 분해들 중 어떤 것도 가질 수 없으며, 여기서부터 정리까지 어떠한 counterrexample도 존재할 수 없다.[4]이 아이디어는 강력한 완벽한 그래프 추측을 암시할 수 있었지만 거짓으로 판명된 유사한 유형의 구조적 분해에 기초했다.[5]

이 구조 분해의 기본 사례를 구성하는 5가지 기본 등급의 완벽한 그래프는 양분 그래프, 양분 그래프의 선 그래프, 양분 그래프의 보완 그래프, 양분 그래프의 선 그래프 보완, 이중 분할 그래프 등이다.초당적 그래프가 완벽하다는 것을 쉽게 알 수 있다: 어떤 비종교적 유도 하위 그래프에서, 클릭 수와 색도 수는 둘 다이고 따라서 둘 다 같다.초당적 그래프의 보완과 초당적 그래프의 선 그래프의 보완 모두 최대 일치, 최대 독립 집합 및 초당적 그래프의 최소 정점 커버의 크기와 관련된 Kőnig의 정리와 동등하다.초당적 그래프의 선 그래프의 완벽성은 K graphsnig(1916년)에 의해 증명된, 초당적 그래프의 색지수 최대치가 된다는 사실로서 동등하게 말할 수 있다.따라서 이 4개의 기본수업은 모두 완벽하다.이중 분할 그래프는 완전하다는 것을 보여줄 수 있는 분할 그래프의 상대적인 것이다.[6]

이 증명에서 고려된 네 가지 유형의 분해는 2-조인, 2-조인, 균형 잡힌 스큐 파티션, 동종 쌍이다.

2-조인은 그래프의 정점을 두 개의 부분 집합으로 분할하는 것으로, 이 두 부분 집합 사이에 절단된 모서리가 두 개의 꼭지점 분리 완전 쌍방향 그래프를 형성하는 속성이 있다.그래프가 2-조인을 가질 때, 두 개의 완전한 쌍방향 그래프 중 하나를 다른 것과 연결하는 부분 집합 내에서 최단 경로로 정점의 두 부분 집합 중 하나를 교체하여 "블록"이라고 불리는 유도 하위 그래프로 분해될 수 있다. 그러한 경로가 없을 때, 블록은 정점의 두 부분 집합 중 하나를 t로 대체하여 대신 형성된다.완전 초당적 서브그래프당 하나씩의 문제 정점.두 블록이 모두 완벽해야 2조인이 완벽하다.따라서 최소 불완전한 그래프가 2-조인을 갖는 경우 블럭 중 하나와 같아야 하며, 여기서부터는 Berge가 아닌 홀수 사이클이어야 한다.같은 이유로, 보완장치가 2조인을 갖는 최소 불완전한 그래프는 버지가 될 수 없다.[7]

스큐 파티션은 그래프 정점을 두 개의 하위 집합으로 분할하는 것으로, 그 중 하나는 분리된 서브그래프를 유도하고 다른 하나는 분리된 보완을 가지고 있다; Chvatal(1985)은 강한 완벽한 그래프 추측에 대한 최소한의 countexample도 스큐 파티션을 가질 수 없다고 추측했다.추드노브스키 외 연구진은 꼬치 파티션에 대한 기술적 제약사항을 소개했고, 이로 인한 "균형된 꼬치 파티션"에 대해 추드탈의 추측이 사실임을 보여줄 수 있었다.완전한 추측은 강력한 완벽한 그래프 정리의 귀결이다.[8]

동질 쌍은 그래프의 모듈식 분해와 관련이 있다.V와1 V가2 함께 최소 3개의 정점을 포함하고, V가3 최소 2개의 정점을 포함하며, V의3 각 정점과 {1,2}의 각 i가 V의i 모든 정점에 인접하거나 그 중 어느 것도 포함하지 않도록 그래프를 세 개의 하위 집합1 V, V23, V로 분할한 것이다.최소한의 불완전한 그래프가 동종 쌍을 갖는 것은 불가능하다.[9]추드노브스키(2006)는 강력한 완벽한 그래프 추측의 입증에 이어, 증명서에 사용된 분해 집합에서 동질 쌍이 제거될 수 있다는 것을 보여줌으로써 그것을 단순화했다.

모든 Berge 그래프가 5가지 기본 등급 중 하나에 속하거나 4가지 유형의 분해 유형 중 하나에 속한다는 증거는 사례 분석을 따르는데, 그래프 안에 특정 구성이 존재하는지 여부: "스트레처(stretcher)", 특정 추가 제약 조건에 따라 3가지 유도 경로로 분해될 수 있는 하위 그래프, 즉 a의 보완.들것, 그리고 휠 그래프와 관련된 구성인 "속성 휠"은 유도 사이클과 최소 3 사이클 정점에 인접하고 몇 가지 추가 제약 조건을 준수하는 허브 정점으로 구성된다.주어진 Berge 그래프 내에 들것이나 들것의 보완물 또는 적절한 바퀴가 존재하는지 여부를 선택할 수 있는 각각의 가능한 선택에 대해, 그래프는 기본 등급 중 하나이거나 분해 가능한 것으로 보일 수 있다.[10]이 사례분석을 통해 그 증거가 완성된다.

메모들

  1. ^ 매켄지(2002);코르네홀스(2002년).
  2. ^ 매켄지(2002년).
  3. ^ "2009 Fulkerson Prizes" (PDF), Notices of the American Mathematical Society: 1475–1476, December 2011.
  4. ^ 코르네홀스(2002년), 추측 5.1.
  5. ^ 리드(1986); 후가르디(1991); 루수(1997); 루셀, 루수 & 툴리에(2009), 섹션 4.6 "첫 번째 추측".
  6. ^ Roussel, Rusu & Thuillier(2009), Definition 4.39.
  7. ^ Cornuéjols & Cunningham(1985); Cornuéjols(2002),정리 3.2와 코롤라리 3.3.
  8. ^ 시모어(2006);Roussel, Rusu & Thuillier(2009), 섹션 4.7 "꼬치 파티션"; Cornuéjols(2002)정리 4.1과 4.2.
  9. ^ 체바탈&스비히(1987년), 코르누에졸스(2002년),정리 4.10.
  10. ^ 코르누에졸스(2002년),이론 5.4, 5.5 및 5.6; 루셀, 루수 & 툴리에(2009)정리 4.42.

참조

외부 링크