스키너만의 추측

Scheinerman's conjecture

수학에서 현재 정리인 스키너만의 추측에 따르면 모든 평면 그래프는 평면에 있는 선 세그먼트 집합의 교차 그래프라고 한다.이러한 추측은 E. R. Scheinerman이 박사 논문(1984년)에서 모든 평면 그래프를 평면 내 단순 곡선 집합의 교차 그래프로 나타낼 수 있다는 초기 결과에 따라 공식화되었다(Ehrlich, Even & Tarjan 1976년).제레미 찰로핀과 다니엘 곤살베스(2009)가 입증했다.

예를 들어, 왼쪽 아래에 표시된 그래프 G는 오른쪽 아래에 표시된 세그먼트 집합의 교차 그래프로 나타낼 수 있다.여기서 G의 정점은 직선 세그먼트로 표시되고 G의 가장자리는 교차점으로 표시된다.

Intersect1.png Intersect2.png

스키너먼은 또한 세 방향만 있는 세그먼트가 3색 그래프를 나타내기에 충분할 것이라고 추측했고, 웨스트(1991)는 유사하게 모든 평면 그래프는 네 방향을 사용하여 나타낼 수 있다고 추측했다.한 그래프가 k 방향만 있는 세그먼트로 표시되고 두 세그먼트가 동일한 선에 속하지 않는 경우, 각 방향에 대해 하나의 색상인 k 색상을 사용하여 그래프를 색칠할 수 있다.따라서 모든 평면 그래프를 4방향으로만 이런 식으로 나타낼 수 있다면, 4색 정리가 뒤따른다.

하트만, 뉴먼 & 지브(1991) 및 드 프레이세이ix, 오소나 데 멘데스 & 파흐(1991)는 모든 초당적 평면 그래프가 수평선과 수직선 세그먼트의 교차 그래프로 표현될 수 있음을 증명했다. 이 결과에 대해서는 Czzowicz, Kranakis & Urrutia(1998)도 참조한다.드 카스트로 외(2002년)모든triangle-free 평면 그래프 선 세그먼트는 오직 세 방향의 교차 그래프로 나타낼 수 있습니다;이 결과 Grötzsch의 정리(Grötzsch 1959년)은triangle-free 평면 그래프 세가지 색으로 물들 수 있습니다. 드 Fraysseix &, Ossona 드 멘데스(2005년)을 증명하는 것은 만약 평면 그래프 G가 될 수 있4- 것을 증명했다.콜분리 주기가 네 가지 색상을 모두 사용하지 않도록 한 다음 G는 세그먼트의 교차 그래프로 표현한다.

찰로핀, 곤살베스 & 오켐(2007)은 평면 그래프가 쌍당 최대 하나의 교차점에서 서로 교차하는 평면 내 단순 곡선의 교차로 그래프 등급인 1-STRING에 있음을 증명했다.이 세분류는 Scheinerman의 추측에 나타나는 세그먼트의 교차 그래프와 Ehrlich 외 연구 결과의 무제한 단순 곡선의 교차 그래프 사이의 중간이다.원 패킹 정리의 일반화로도 볼 수 있는데, 이는 곡선이 접선에서 교차하도록 허용했을 때 동일한 결과를 보여준다.찰로핀&곤살브스(2009)의 추측에 대한 증명은 이 결과의 개선에 근거한 것이었다.

참조

  • De Castro, N.; Cobos, F. J.; Dana, J. C.; Márquez, A. (2002), "Triangle-free planar graphs as segment intersection graphs" (PDF), Journal of Graph Algorithms and Applications, 6 (1): 7–26, doi:10.7155/jgaa.00043, MR 1898201.
  • Chalopin, J.; Gonçalves, D. (2009), "Every planar graph is the intersection graph of segments in the plane" (PDF), ACM Symposium on Theory of Computing.
  • Chalopin, J.; Gonçalves, D.; Ochem, P. (2007), "Planar graphs are in 1-STRING", Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM and SIAM, pp. 609–617.
  • Czyzowicz, J.; Kranakis, E.; Urrutia, J. (1998), "A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments", Information Processing Letters, 66 (3): 125–126, doi:10.1016/S0020-0190(98)00046-5.
  • de Fraysseix, H.; Ossona de Mendez, P. (2005), "Contact and intersection representations", in Pach, J. (ed.), Graph Drawing, 12th International Symposium, GD 2004, Lecture Notes in Computer Science, vol. 3383, Springer-Verlag, pp. 217–227.
  • de Fraysseix, H.; Ossona de Mendez, P.; Pach, J. (1991), "Representation of planar graphs by segments", Intuitive Geometry, 63: 109–117, MR 1383616.
  • Ehrlich, G.; Even, S.; Tarjan, R. E. (1976), "Intersection graphs of curves in the plane", Journal of Combinatorial Theory, Series B, 21 (1): 8–20, doi:10.1016/0095-8956(76)90022-8, MR 0505857.
  • Grötzsch, Herbert (1959), "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel", Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe, 8: 109–120, MR 0116320.
  • Hartman, I. B.-A.; Newman, I.; Ziv, R. (1991), "On grid intersection graphs", Discrete Mathematics, 87 (1): 41–52, doi:10.1016/0012-365X(91)90069-E, MR 1090188.
  • Scheinerman, E. R. (1984), Intersection Classes and Multiple Intersection Parameters of Graphs, Ph.D. thesis, Princeton University.
  • West, D. (1991), "Open problems #2", SIAM Activity Group Newsletter in Discrete Mathematics, 2 (1): 10–12.