Індиферентний граф

Заборонені породжені підграфи для індиферентних графів — клешня, «сонце», «мережа» і цикли довжиною чотири і більше (внизу)

Скінченні індиферентні графи можна еквівалентно описати як

• Графи перетинів одиничних відрізків[1]
• Графи перетинів множин інтервалів, ніякі два з яких не вкладені один в інший[1][2]
• Інтервальні графи без клешень[1][2]
• Графи, які не містять породжених підграфів, ізоморфних клешні K_1,3, «мережі» (трикутнику з трьома додатковими вершинами, приєднаними до кожної з вершин трикутника), «сонцю» (трикутнику з трьома приєднаними трикутниками, які мають спільні ребра з центральним трикутником), або «дірці» (циклу довжини чотири і більше)[3]
• Графи непорівнянності напівпорядків[1]
• Неорієнтовані графи, які мають лінійний порядок, такий, що для кожного шляху з трьох вершин ${\displaystyle uvw}$, вершини якого впорядковані ${\displaystyle u}$-${\displaystyle v}$-${\displaystyle w}$, кінцеві вершини ${\displaystyle u}$ і ${\displaystyle w}$ суміжні[4]
• Графи, які не мають астральних трійок, трьох вершин, з'єднаних попарно шляхами, які не проходять через третю вершину, а також не містять двох суміжних вершин, одночасно суміжних вершині з околу третьої вершини[5].
• Графи, в яких кожна компонента містить шлях, у якому кожна кліка компоненти утворює неперервний підшлях[6]
• Графи, вершини яких можна пронумерувати так, що будь-який найкоротший шлях утворює монотонну послідовність[6]
• Графи, матриці суміжності яких можна впорядкувати так, що в кожному рядку і кожному стовпці ненульові елементи утворюють неперервні інтервали, суміжні діагоналі матриці[7]
• Породжені підграфи степенів безхордових шляхів[8]
• Листкові степені, які мають листковий корінь у вигляді гусениці[8]

Для нескінченних графів деякі з цих визначень можуть дати різні графи.

Оскільки індиферентні графи є окремим випадком інтервальних графів, індиферентні графи мають усі властивості інтервальних графів. Зокрема, вони є окремим випадком хордальних графів і досконалих графів. Ці графи є також окремим випадком колових графів, що хибно для інтервальних графів загального вигляду.

У моделі Ердеша — Реньї випадкових графів граф з ${\displaystyle n}$ вершини, число ребер якого істотно менше від ${\displaystyle n^{2/3}}$, буде з великою ймовірністю індиферентним графом, тоді як граф з числом ребер, істотно більшим від ${\displaystyle n^{2/3}}$, з великою ймовірністю не буде індиферентним графом[9].

Ширина стрічки довільного графу ${\displaystyle G}$ на одиницю менша від розміру найбільшої кліки в індиферентному графі, який містить ${\displaystyle G}$ як підграф і вибраний для мінімізації розміру найбільшої кліки[10]. Це властивість утворює паралелі, подібні до зв'язку між шляховою шириною та інтервальними графами, а також між деревною шириною та хордальними графами. Слабше поняття ширини, клікова ширина, може бути довільно великою на індиферентних графах[11]. Однак будь-який власний підклас індиферентних графів, не замкнутий відносно породжених підграфів, має обмежену клікову ширину[12].

Будь-який зв'язний індиферентний граф містить гамільтонів шлях[13]. Індиферентний граф має гамільтонів граф тоді і тільки тоді, коли він двосв'язний[14].

Індиферентні графи задовольняють гіпотезі про реконструкцію — вони єдиним чином визначаються їхніми підграфами з видаленою вершиною[15].

Як і з багатовимірними графами одиничних кругів, можна перетворити множину точок на її індиферентний граф або множину одиничних відрізків на її граф одиничних відрізків за лінійний час, якщо вимірювати в термінах розміру початкового графу. Алгоритм округлює точки (або центри інтервалів) до найближчого меншого цілого числа, використовує геш-таблицю для знаходження всіх пар точок, чиї округлені значення відрізняються не більше ніж на одиницю (пошук найближчого сусіда з фіксованим радіусом), і відбирає в отриманому списку пари, неокруглені значення яких лежать не далі ніж на одиницю одне від одного[16].

Можна перевірити, чи є даний граф індиферентним за лінійний час за допомогою PQ-дерев для побудови інтервальних подань графу і потім перевірки, чи задовольняє впорядкування вершин, похідне від цього подання, властивостям індиферентного графу[4]. Можна також заснувати алгоритм розпізнавання для індиферентних графів на алгоритмах розпізнавання для хордального графу[14]. Деякі альтернативні алгоритми розпізнавання за лінійний час ґрунтуються на пошуку в ширину або на лексикографічному пошуку в ширину, а не на зв'язку між індиферентними графами і інтервальними графами[17][18] [19][20].

Як тільки вершини відсортовано за їхніми числовими значеннями, які описують індиферентний граф (або за послідовністю одиничних відрізків у інтервальному поданні), той самий порядок можна використовувати для пошуку оптимального розфарбування цих графів, щоб розв'язати задачу про найкоротший шлях, побудову гамільтонових шляхів і найбільших парувань за лінійний час[4]. Гамільтонів цикл можна знайти з правильного інтервального графу подання за час ${\displaystyle O(n\log n)}$[13], але, якщо граф є вхідним для завдання, цю ж задачу можна розв'язати за лінійний час, що можна узагальнити на інтервальні графи[21][22] .

Задача спискового розфарбовування залишається NP-повною, навіть коли вона обмежена індиферентними графами[23]. Однак вона є фіксовано-параметрично розв'язною, якщо параметризувати за загальною кількістю кольорів на вході[12].

У математичній психології індиферентні графи виникають із функцій корисності масштабуванням функції так, що одна одиниця представляє різницю корисності досить малою, так що для особистості одиниця може вважатися несуттєвою. У цьому застосуванні пари елементів, корисності яких досить великі, можна частково впорядкувати за відносним порядком корисності, що дає напівпорядок[1][24].

У біоінформатиці задачу додавання розфарбованого графу до правильно розфарбованого графу одиничних відрізків можна використати для моделювання виявлення помилково негативних збірок геному ДНК із фрагментів[25].

• Пороговий граф — граф, ребра якого визначаються сумами міток вершин, а не різницями міток
• Тривіально досконалий граф — інтервальний граф, для якого кожна пара інтервалів вкладена або неперервана, а не належним чином перетинається

• Information System on Graph Class Inclusions: unit interval graph