Гіпо́теза ШейнерманаПрізвище німецького походження і німецькою воно має звучати «Шайнерман», проте цей математик зі США., тепер доведена теорема, стверджує, що будь-який планарний граф є графом перетинів набору відрізків на площині. Цю гіпотезу сформулював у своїй кандидатській дисертації, спираючись на раніший результат, що будь-який планарний граф можна подати як граф перетинів простих кривих на площині. Теорему довели Чалопін і Гонсалвіс.

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

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

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

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

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

Примітки

Література