선완전 그래프

Line perfect graph
선 완벽한 그래프.각 이코넥트 성분의 가장자리는 초당적 성분의 경우 검은색, 성분의 4면체의 경우 파란색, 성분의 3각형의 성분의 경우 빨간색이다.

그래프 이론에서 선 완료 그래프는 선 그래프가 완벽한 그래프인 그래프다.동등하게, 이것들은 모든 홀수 길이의 단순 주기가 삼각형인 그래프들이다.[1]

, 만약 각biconnected 구성 요소의 양분 그래프, 완전 그래프 K4{\displaystyle K_{4}}, 또는 삼각형 책 K1,1, n{\displaystyle K_{1,1,n}}.[2]왜냐하면biconnected 구성 요소의 세가지 형태는 모두 완벽한 그래프, 모든 선은 완벽 그래프 자체가 있는 그래프 라인 완벽하다. 당fect.[1] 비슷한 추론에 의해 모든 선 완벽한 그래프는 패리티 그래프,[3] 메이니엘 그래프,[4] 그리고 완벽하게 주문 가능한 그래프다.

선 완성도 그래프는 초당적 그래프를 일반화하고, 최대 일치도와 최소 꼭지점 커버의 크기가 같고 색도 지수가 최대도와 같다는 속성을 공유한다.[5]

참고 항목

참조

  1. ^ a b Trotter, L. E., Jr. (1977), "Line perfect graphs", Mathematical Programming, 12 (2): 255–259, doi:10.1007/BF01593791, MR 0457293
  2. ^ Maffray, Frédéric (1992), "Kernels in perfect line-graphs", Journal of Combinatorial Theory, Series B, 55 (1): 1–8, doi:10.1016/0095-8956(92)90028-V, MR 1159851.
  3. ^ Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, p. 281, doi:10.1007/978-3-642-78240-4, ISBN 3-540-56740-2, MR 1261419.
  4. ^ Wagler, Annegret (2001), "Critical and anticritical edges in perfect graphs", Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14–16, 2001, Proceedings, Lecture Notes in Computer Science, vol. 2204, Berlin: Springer, pp. 317–327, doi:10.1007/3-540-45477-2_29, MR 1905643.
  5. ^ de Werra, D. (1978), "On line-perfect graphs", Mathematical Programming, 15 (2): 236–238, doi:10.1007/BF01609025, MR 0509968.