켈만-시모어 추측

Kelmans–Seymour conjecture
12-Vertex 크라운 그래프의 K 하위5 분할

그래프 이론에서 켈만족은–시모어 추측에 따르면 평면도가 아닌 모든 5Vertex 연결 그래프에는 5Vertex 전체 그래프 K의5 하위분할이 포함되어 있다.그것은 폴 세이모어와 알렉산더 켈만스의 이름을 따서 지어졌는데, 그는 그 추측을 독립적으로 기술했고, 1977년에는 세이모어, 1979년에는 켈만스를 기술했다.[1][2]증거가 발표되었지만 아직 발표되지 않았다.[1][3]

공식화

제거된 그래프가 분리된 정점이 5개 없을 때 그래프는 5Vertex 연결된다.전체 그래프는 5개의 꼭지점 사이에 가장자리가 있는 그래프로, 전체 그래프의 하위 분할은 가장자리의 일부를 더 긴 경로로 대체함으로써 이를 수정한다.그래서 그래프 G는 G의 5개의 정점을 고를 수 있다면 K의5 하위분할을 포함하고, 정점이나 가장자리를 서로 공유하는 어떤 경로도 없이 이들 5개의 정점을 쌍으로 연결하는 10개의 경로 집합을 포함한다.

유클리드 평면에 있는 그래프의 어떤 도면에서도 10개의 경로 중 적어도 2개는 교차해야 하므로 K분할을5 포함하는 그래프 G는 평면 그래프가 될 수 없다.다른 방향에서 쿠라토프스키의 정리로는 평면도가 아닌 그래프는 반드시 K의5 하위분할이나 완전한3,3 양분 그래프 K의 하위분할을 포함하고 있다.켈맨스 가족–시모어 추측에서는 이 두 소분류 중 K의5 소분류 중 하나만 존재할 수 있는 조건을 제시함으로써 이 정리를 재조명한다.비 평면 그래프가 5Vertex로 연결된 경우 K의5 소분할을 포함한다고 명시되어 있다.

관련결과

이와 관련된 결과인 바그너의 정리에는 4Vertex로 연결된 비플래너 그래프마다 그래프 마이너로서5 K의 복사본이 포함되어 있다고 명시되어 있다.이 결과를 재작성하는 한 가지 방법은 이 그래프에서 결과 그래프가 K5 하위분할을 포함하도록 에지 수축 연산의 순서를 수행하는 것이 항상 가능하다는 것이다.켈맨스 가족–시모어 추측에 따르면 연결의 질서가 높으면 이러한 수축이 필요하지 않다.

볼프강 마더에 의해 2001년에 입증된 가브리엘 앤드류 디락(1964)에 대한 이전의 추측에 따르면, 모든 n-vertex 그래프에 적어도 3n - 5 에지가 있는 K의5 분열이 포함되어 있다고 한다.평면 그래프는 최대 3n - 6개의 가장자리를 가지므로 3n - 5개의 가장자리를 가진 그래프는 평면도가 아니어야 한다.단, 5-연결할 필요는 없으며, 5-연결 그래프는 2.5n 에지까지 가질 수 있다.[4][5][6]

청구증거

2016년 켈만족의 증거–시모어 추측은 조지아 공대의 싱싱 유 교수와 그의 박사과정 학생인 다웨이 허 교수와 옌 왕 교수가 주장하였다.[3]이 추측을 증명하는 연속 4개의 논문이 Journal of Combinatorial 이론, Series B에 실렸다.[7][8][9][10]

참고 항목

참조

  1. ^ a b Condie, Bill (May 30, 2016), "Maths mystery solved after 40 years", Cosmos.
  2. ^ 그러나 Thomassen(1997)은 세이모어의 추측 공식화 날짜를 1984년으로 정했다는 점에 주목한다.
  3. ^ a b 그는, 다웨이, 왕, 연, 유, Xingxing(11월 16일 2015년), 그 Kelmans.–Seymour 추측 나는:특별한 분리, arXiv:1511.05020, ——, et 알.(2월 24일 2016년), 그 Kelmans.–Seymour 추측 2:K4−{\displaystyle K_{4}^{-}에 2-vertices}, arXiv:1602.07557, ——, et 알.(9월 19일 2016년), 그 Kelmans.–Seymour 추측 III:K4−{\displaystyle K_{4}^{-}에 3-vertices}, arXiv:1609.05747, ——, et 알.(12월 21일 2016년), 그 Kelmans.–Seymour 추측 IV:증명, arXiv:1612.07189.
  4. ^ Dirac, G. A. (1964), "Homomorphism theorems for graphs", Mathematische Annalen, 153: 69–80, doi:10.1007/BF01361708, MR 0160203, S2CID 121213793
  5. ^ Thomassen, Carsten (1997), "Dirac's conjecture on -subdivisions", Discrete Mathematics, 165/166: 607–608, doi:10.1016/S0012-365X(96)00206-3, MR 1439305
  6. ^ Mader, W. (1998), " edges do force a subdivision of ", Combinatorica, 18 (4): 569–595, doi:10.1007/s004930050041, MR 1722261, S2CID 7311121
  7. ^ He, Dawei; Wang, Yan; Yu, Xingxing (2019-12-11). "The Kelmans-Seymour conjecture I: Special separations". Journal of Combinatorial Theory, Series B. 144: 197–224. arXiv:1511.05020. doi:10.1016/j.jctb.2019.11.008. ISSN 0095-8956. S2CID 29791394.
  8. ^ He, Dawei; Wang, Yan; Yu, Xingxing (2019-12-11). "The Kelmans-Seymour conjecture II: 2-Vertices in K4−". Journal of Combinatorial Theory, Series B. 144: 225–264. arXiv:1602.07557. doi:10.1016/j.jctb.2019.11.007. ISSN 0095-8956.
  9. ^ He, Dawei; Wang, Yan; Yu, Xingxing (2019-12-09). "The Kelmans-Seymour conjecture III: 3-vertices in K4−". Journal of Combinatorial Theory, Series B. 144: 265–308. arXiv:1609.05747. doi:10.1016/j.jctb.2019.11.006. ISSN 0095-8956. S2CID 119625722.
  10. ^ He, Dawei; Wang, Yan; Yu, Xingxing (2019-12-19). "The Kelmans-Seymour conjecture IV: A proof". Journal of Combinatorial Theory, Series B. 144: 309–358. arXiv:1612.07189. doi:10.1016/j.jctb.2019.12.002. ISSN 0095-8956. S2CID 119175309.