메이니엘 그래프

Meyniel graph
Meyniel 그래프에서, 모든 긴 홀수 사이클(예: 여기에 표시된 검은색 5 사이클)은 적어도 두 개의 화음(녹색)을 가져야 한다.

그래프 이론에서, 메이니엘 그래프는 길이 5 이상의 모든 홀수 사이클이 적어도 두 개의 화음을 갖는 그래프로, 즉 사이클의 비정점들을 연결하는 가장자리를 가지고 있다.[1]화음은 (그림에 나타난 바와 같이) 합이 없을 수도 있고, 두 개 이상의 화음이 있는 한 서로 교차할 수도 있다.

메이니엘 그래프는 헨리 메이니엘(메이니엘의 추측으로도 알려져 있다)의 이름을 따온 것으로, 강력한 완벽한 그래프 정리의 증거가 완벽한 그래프를 완벽하게 특징 짓기 훨씬 전인 1976년에 완벽한 그래프임을 증명했다.[2]같은 결과가 마르코스잔과 카라페잔(1976년)에 의해 독자적으로 발견되었다.[3]

완벽

메이니엘 그래프는 완벽한 그래프의 하위 클래스다.메이니엘 그래프의 모든 유도 하위 그래프는 또 다른 메이니엘 그래프인데, 모든 메이니엘 그래프에서 최대 클라이크의 크기는 그래프 컬러링에 필요한 최소 색상 수와 같다.따라서, 메이니엘 그래프는 완벽한 그래프라는 정의를 충족하며, 클릭 숫자는 모든 유도 서브그래프에서 색수와 같다는 것을 의미한다.[1][2][3]

왜냐하면(로 Meyniel과 Hoàng을 증명했다 추측했다)그들은 속성은 강하게 완벽한 그래프의 결정적인 속성을 일반화에 의해:Meyniel 그래프의 모든 유도 부분 그래프에, 모든 꼭지점마다 최대 파벌을 독립적인 세트의 일부이다 특징을 나타낼 수 있으며 Meyniel 그래프도 아주 강하게 완벽한 그래프라고 부른다.[1][4]

관련 그래프 클래스

메이니엘 그래프에는 화음 그래프, 패리티 그래프가 들어 있으며, 그 하위 분류에는 구간 그래프, 거리-계통 그래프, 양분 그래프, 선 완벽 그래프 등이 있다.[1]

하우스 그래프는 완벽하지만 메이니엘은 완벽하지 않다.

메이니엘 그래프는 완벽한 그래프의 매우 일반적인 하위 클래스를 형성하지만, 모든 완벽한 그래프를 포함하지는 않는다.예를 들어 하우스 그래프(현재가 하나뿐인 펜타곤)는 완벽하지만 메이니엘 그래프는 아니다.

알고리즘 및 복잡성

Meyniel 그래프는 다항 시간 내에 인식할 수 있으며,[5] 임의 그래프의 경우 NP-hard인 그래프 컬러링 등 여러 그래프 최적화 문제는 Meyniel 그래프의 다항 시간 내에 해결할 수 있다.[6][7]

참조

  1. ^ a b c d Meyniel graphs on Graph Classs and the Includementals on Graph Classes and the Includementations, 2016-09-25를 검색했다.
  2. ^ a b Meyniel, H. (1976), "On the perfect graph conjecture", Discrete Mathematics, 16 (4): 339–342, doi:10.1016/S0012-365X(76)80008-8, MR 0439682.
  3. ^ a b Markosjan, S. E.; Karapetjan, I. A. (1976), "Perfect graphs", Doklady Akademiya Nauk Armyanskoĭ SSR, 63 (5): 292–296, MR 0450130.
  4. ^ Hoàng, C. T. (1987), "On a conjecture of Meyniel", Journal of Combinatorial Theory, Series B, 42 (3): 302–312, doi:10.1016/0095-8956(87)90047-5, MR 0888682.
  5. ^ Burlet, M.; Fonlupt, J. (1984), "Polynomial algorithm to recognize a Meyniel graph", Topics on perfect graphs, North-Holland Math. Stud., vol. 88, North-Holland, Amsterdam, pp. 225–252, doi:10.1016/S0304-0208(08)72938-4, hdl:10068/49205, MR 0778765.
  6. ^ Hertz, A. (1990), "A fast algorithm for coloring Meyniel graphs", Journal of Combinatorial Theory, Series B, 50 (2): 231–240, doi:10.1016/0095-8956(90)90078-E, MR 1081227.
  7. ^ Roussel, F.; Rusu, I. (2001), "An O(n2) algorithm to color Meyniel graphs", Discrete Mathematics, 235 (1–3): 107–123, doi:10.1016/S0012-365X(00)00264-8, MR 1829840.