Гіпотеза Шейнермана

Гіпо́теза Шейнермана[1], тепер доведена теорема, стверджує, що будь-який планарний граф є графом перетинів набору відрізків на площині. Цю гіпотезу сформулював Едвард Шейнерман[en] у своїй кандидатській дисертації[2], спираючись на раніший результат, що будь-який планарний граф можна подати як граф перетинів простих кривих на площині[3]. Теорему довели Чалопін і Гонсалвіс[4].

Приклад

Граф G, показаний нижче ліворуч можна подати як граф перетинів набору відрізків, показаних праворуч. Тут вершини графа G подано відрізками, а ребра графа G подано точками перетинів цих відрізків.

 

Розвиток

Шейнерман також висловив гіпотезу, що достатньо мати відрізки трьох напрямків для подання розфарбовуваних у 3 кольори графів, а Вест[5] висловив гіпотезу, що, аналогічно, будь-який планарний граф можна подати за допомогою відрізків чотирьох напрямків. Якщо граф подаваний відрізками, що мають тільки k напрямків, і ніякі два відрізки не лежать на одній прямій, граф можна розфарбувати за допомогою k кольорів, по одному кольору на кожен напрямок. Тому, якщо будь-який планарний граф можна подати таким способом тільки з чотирма напрямками відрізків, звідси випливатиме теорема про чотири фарби.

Гартман, Ньюман і Зів[6], а також Де Фрейсікс, Оссона де Мендез і Пах[7], довели, що будь-який двочастинний планарний граф можна подати як граф перетинів горизонтальних і вертикальних відрізків (див. про це статтю Чижовича, Кранакіса та Уррутія[8]). Де Кастро, Кобос, Дана і Маркес[9] довели, що будь-який вільний від трикутників планарний граф можна подати як граф перетинів відрізків, що мають усього три напрямки. З їхнього результату випливає теорема Ґрьоча[10], що вільний від трикутників планарний граф можна розфарбувати в три кольори. Де Фрейсікс і Оссона де Мендез[11] довели, що якщо планарний граф G можна розфарбувати в 4 кольори так, що ніякий розділювальний цикл не використовує всіх чотирьох кольорів, то граф G можна подати як граф перетинів відрізків.

Струнні графи

Докладніше: Струнний граф

Чалопін, Гонсалвіс і Очем[12] довели, що планарні графи знаходяться в класі 1-струн, класі графів перетинів простих кривих на площині, які перетинають одна одну максимум один раз на пару кривих. Цей клас є середнім між графами перетинів відрізків, що з'являються в гіпотезі Шейнермана, і графами перетинів простих кривих без обмежень з результатів Ерліха (зі співавторами). Гіпотезу можна розглядати як узагальнення теореми про пакуваня кіл, яка дає той самий результат, коли криві можуть тільки дотикатися між собою. Доведення гіпотези, яке надали Чалопін і Гонсалвіс[4] базувалося на поліпшенні цього результату.

Примітки

  1. ↑ Прізвище німецького походження і німецькою воно має звучати «Шайнерман», проте цей математик зі США.
  2. ↑ Scheinerman, 1984.
  3. ↑ Ehrlich, Even, Tarjan, 1976.
  4. ↑ а б Chalopin, Gonçalves, 2009.
  5. ↑ West, 1991.
  6. ↑ Hartman, Newman, Ziv, 1991.
  7. ↑ de Fraysseix, Ossona de Mendez, Pach, 1991.
  8. ↑ Czyzowicz, Kranakis, Urrutia, 1998.
  9. ↑ De Castro, Cobos, Dana, Márquez, 2002.
  10. ↑ Grötzsch, 1959.
  11. ↑ de Fraysseix, Ossona de Mendez, 2005.
  12. ↑ Chalopin, Gonçalves, Ochem, 2007.

Література

  • De Castro N., Cobos F. J., Dana J. C., Márquez A. Triangle-free planar graphs as segment intersection graphs // Journal of Graph Algorithms and Applications. — 2002. — Т. 6, вип. 1 (25 грудня). — С. 7–26. — DOI:10.7155/jgaa.00043. Архівовано з джерела 3 грудня 2008. Процитовано 25 березня 2022.
  • Chalopin J., Gonçalves D. ACM Symposium on Theory of Computing. — 2009.
  • Chalopin J., Gonçalves D., Ochem P. Planar graphs are in 1-STRING // Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. — ACM and SIAM, 2007. — С. 609–617.
  • Czyzowicz J., Kranakis E., Urrutia J. A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments // Information Processing Letters. — 1998. — Т. 66, вип. 3 (25 грудня). — С. 125–126. — DOI:10.1016/S0020-0190(98)00046-5.
  • de Fraysseix H., Ossona de Mendez P. Graph Drawing, 12th International Symposium, GD 2004. — Springer-Verlag, 2005. — Т. 3383. — С. 217–227. — (Lecture Notes in Computer Science)
  • de Fraysseix H., Ossona de Mendez P., Pach J. Representation of planar graphs by segments // Intuitive Geometry. — 1991. — Т. 63 (25 грудня). — С. 109–117.
  • Ehrlich G., Even S., Tarjan R. E. Intersection graphs of curves in the plane // Journal of Combinatorial Theory. — 1976. — Т. 21, вип. 1 (25 грудня). — С. 8–20. — (Series B). — DOI:10.1016/0095-8956(76)90022-8.
  • Herbert Grötzsch. 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. — 1959. — Т. 8 (25 грудня). — С. 109–120.
  • Hartman I. B.-A., Newman I., Ziv R. On grid intersection graphs // Discrete Mathematics. — 1991. — Т. 87, вип. 1 (25 грудня). — С. 41–52. — DOI:10.1016/0012-365X(91)90069-E.
  • Scheinerman E. R. Intersection Classes and Multiple Intersection Parameters of Graphs. — Princeton University, 1984. — (Ph.D. thesis)
  • West D. Open problems #2 // SIAM Activity Group Newsletter in Discrete Mathematics. — 1991. — Т. 2, вип. 1 (25 грудня). — С. 10–12.