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

В математике , гипотеза Шайнермана ставшая теперь теоремой, утверждает, что каждый плоский граф является графом пересечения набора отрезков прямой на плоскости. Эту гипотезу сформулировал Э.Р. Шейнерман в своей докторской диссертации. диссертация (1984 г.) , следуя более ранним результатам о том, что каждый плоский граф может быть представлен как граф пересечений набора простых кривых на плоскости ( Эрлих, Эвен и Тарьян, 1976 г. ). Это доказали Жереми Чалопен и Даниэль Гонсалвес ( 2009 ).

Например, граф G, показанный ниже слева, может быть представлен как граф пересечений набора сегментов, показанных ниже справа. Здесь вершины G ребра представлены отрезками прямых, а G представлены . точками пересечения

 

Шайнерман также предположил, что сегментов только с тремя направлениями будет достаточно для представления графов, раскрашиваемых в 3 цвета , а Уэст (1991) предположил, что аналогичным образом каждый планарный граф можно представить с использованием четырех направлений. Если граф представлен сегментами, имеющими только k направлений и никакие два отрезка не принадлежат одной прямой, то граф можно раскрасить в k цветов, по одному цвету для каждого направления. Следовательно, если каждый планарный граф можно представить таким образом только с четырьмя направлениями, затем следует теорема о четырех цветах . Гонсалвес (2020) доказал, что некоторые плоские графы невозможно представить таким образом.

Хартман, Ньюман и Зив (1991) и де Фрессейкс, Оссона де Мендес и Пах (1991) доказали, что каждый двудольный плоский граф может быть представлен как граф пересечения горизонтальных и вертикальных отрезков; об этом результате см. также Czyzowicz, Kranakis & Urrutia (1998) . Де Кастро и др. (2002) доказали, что каждый планарный граф без треугольников можно представить как граф пересечений отрезков прямой, имеющих только три направления; из этого результата следует теорема Греча ( Grötzsch 1959 ) о том, что плоские графы без треугольников можно раскрасить в три цвета. де Фрайссейкс и Оссона де Мендес (2005) доказали, что если планарный граф G может быть 4-цветным таким образом, что ни один разделяющий цикл не использует все четыре цвета, то G имеет представление в виде графа пересечений сегментов.

Chalopin, Gonçalves & Ochem (2007) доказали, что плоские графы относятся к 1-STRING, классу графов пересечений простых кривых на плоскости, которые пересекаются друг с другом не более чем в одной точке пересечения на пару. Этот класс занимает промежуточное положение между графами пересечений отрезков, возникающими в гипотезе Шейнермана, и графами пересечений неограниченных простых кривых из результата Эрлиха и др. Ее также можно рассматривать как обобщение теоремы об упаковке кругов , которая показывает тот же результат, когда кривым разрешено пересекаться по касательной. Доказательство гипотезы Чалопина и Гонсалвеса (2009) было основано на улучшении этого результата.

Ссылки

• Де Кастро, Н.; Кобос, Ф.Дж.; Дана, Джей Си; Маркес, А. (2002), «Плоские графы без треугольников как графы пересечения сегментов» (PDF) , Журнал графовых алгоритмов и приложений , 6 (1): 7–26, doi : 10.7155/jgaa.00043 , MR   1898201 .
• Чалопин Дж.; Гонсалвес, Д. (2009), «Каждый плоский граф представляет собой граф пересечения сегментов на плоскости» (PDF) , Симпозиум ACM по теории вычислений .
• Чалопин Дж.; Гонсалвес, Д.; Очем, П. (2007), «Плоские графы имеют 1-СТРУНУ», Труды восемнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , ACM и SIAM, стр. 609–617 .
• Чизович, Дж.; Кранакис, Э.; Уррутия, Дж. (1998), «Простое доказательство представления двудольных плоских графов в виде контактных графов ортогональных отрезков прямых», Information Processing Letters , 66 (3): 125–126, doi : 10.1016/S0020-0190 (98)00046-5 .
• де Фрейссе, Х.; Оссона де Мендес, П. (2005), «Представления контактов и пересечений», в Пах, Дж. (ред.), Рисование графиков, 12-й Международный симпозиум, GD 2004 , Конспекты лекций по информатике, том. 3383, Springer-Verlag, стр. 217–227 .
• де Фрейссе, Х.; Оссона де Мендес, П. ; Пах, Дж. (1991), «Представление плоских графов сегментами», Интуитивная геометрия , 63 : 109–117, MR   1383616 .
• Эрлих, Г.; Эвен, С.; Тарьян, Р.Э. (1976), «Графики пересечения кривых на плоскости», Журнал комбинаторной теории , серия B, 21 (1): 8–20, doi : 10.1016/0095-8956(76)90022-8 , MR   0505857 .
• Гретч, Герберт (1959), «К теории дискретных сущностей, VII: теорема о трех цветах для сетей без трехкругов на сфере», Wiss. З. Мартин-Лютер-У., Галле-Виттенберг, Math.-Nat. Серия , 8 : 109–120, МР   0116320 .
• Хартман, IB-A.; Ньюман, И.; Зив, Р. (1991), «О графах пересечения сеток», Discrete Mathematics , 87 (1): 41–52, doi : 10.1016/0012-365X(91)90069-E , MR   1090188 .
• Шайнерман, Э.Р. (1984), Классы пересечений и множественные параметры пересечений графов , доктор философии. диссертация, Принстонский университет .
• Уэст, Д. (1991), «Открытые проблемы № 2», Информационный бюллетень группы деятельности SIAM по дискретной математике , 2 (1): 10–12 .
• Гонсалвес, Дэниел (2020), «Не все плоские графы находятся в PURE-4-DIR», Журнал графовых алгоритмов и приложений , 24 (3): 293–301, doi : 10.7155/jgaa.00533 .