Перегляд вихідного коду сторінки Граф без клешень

У [[Теорія графів|теорії графів]] '''графом без клешень''' називається граф, який не містить [[Зірка (теорія графів)|клешень]], як [[Породжений підграф|породжених підграфів]].

[[Файл:Complete bipartite graph K3,1.svg|thumb|164x164px|Клешня]]'''Клешнею''' називається [[Двочастковий граф|повний двочастковий граф]] ''K''<sub>1,3</sub> (тобто, [[Зірка (теорія графів)|зірка]] з трьома ребрами, трьома листками і однією центральною вершиною). Граф без клешень&nbsp;— це граф, в якому кожен [[породжений підграф]] не є клешнею. Тобто будь-яка підмножина з чотирьох вершин не є зіркою з трьома ребрами, що виходять з центральної вершини. Також можливо визначити граф без клешень, як граф, в якому [[Окіл (теорія графів)|окіл]] будь-якої [[Вершина (теорія графів)|вершини]] утворює [[Доповнення графу|доповнення]] [[Граф без трикутників|графу без трикутників]].

Графи без клешень спочатку вивчалися як узагальнення [[Реберний граф|реберних графів]] і викликали додатковий інтерес лише тоді, коли було зроблено три ключових відкриття про графи без клешень:
# усі [[Зв'язний граф|зв'язні]] графи без клешень парного порядку мають [[Парування (теорія графів)|досконалі парування]];
# відкриття [[Теорія складності обчислень|поліноміального за часом]] алгоритму пошуку [[Задача про незалежну множину#Максимальна незалежна множина в дереві|максимальних незалежних множин]] у графах без клешень;
# опис [[Досконалий граф|досконалих графів]] без клешень{{sfn|Faudree, Flandrin, Ryjáček|1997|p=88}};
Графам без клешень присвячені сотні статей і кілька оглядів{{sfn|Faudree, Flandrin, Ryjáček|1997|}}.

== Приклади ==
[[Файл:Icosahedron.svg|thumb|150px|Правильний ікосаедр, багатогранник, вершини і ребра якого формують граф без клешень.]]
* [[Реберний граф]] ''L''(''G'') будь-якого графу ''G'' не має клешень. ''L''(''G'') містить вершину для кожної дуги ''G'' , і вершини є суміжними в ''L''(''G'') коли відповідні ребра мають спільну вершину в ''G''. Реберний граф ''L''(''G'') не може мати клешень, оскільки, якщо кожне з трьох ребер ''e<sub>1</sub>'', ''e<sub>2</sub>'', і ''e<sub>3</sub>'' графу ''G'' має загальну вершину з четвертим ребром ''e<sub>4</sub>'', то згідно з [[Принцип Діріхле|принципом Діріхле]] щонайменше 2 ребра з ''e<sub>1</sub>'', ''e<sub>2</sub>'', і ''e<sub>3</sub>'' мають спільну вершину. Реберні графи можуть бути описані дев'ятьма [[Характеризація забороненими графами|забороненими підграфами]]<ref>{{Стаття|автор = L. W. Beineke|contribution = Derived graphs of digraphs|editor1-last = Sachs | editor1-first = H.|editor2-last = Voss | editor2-first = H.-J.|editor3-last = Walter | editor3-first = H.-J.|location = Leipzig|сторінки = 17—33|видавництво = Teubner| заголовок= Beiträge zur Graphentheorie|рік = 1968}}</ref>, і клешня є найпростішим з цих дев'яти графів. Це дає мотив для вивчення графів без клешень{{sfn|Faudree, Flandrin, Ryjáček|1997|p=88}}.
* {{Нп|Граф де Брейна||en|De Bruijn graph}} (графи, вершини яких відповідають n-бітовим двійковим рядкам для деякого n, а дуги відповідають (n−1)-бітним збігам двох рядків) не мають клешень. Один із способів показати це&nbsp;— побудувати граф де Бройна для n-бітових рядків як реберний граф від графу де Брейна для (n−1)-бітних рядків.
* [[Доповнення графу|Доповнення]] будь-якого графу без трикутників не має клешень{{sfn|Faudree, Flandrin, Ryjáček|1997|p=89}}. Ці графи включають будь-який [[повний граф]] як особливий випадок.
* {{Нп|Належний інтервальний граф|Належні інтервальні графи|en|Proper interval graph}}<!-- Проблема вікіфікації: Сторінка [[:en:Proper interval graph]] (→ [[:en:Indifference graph]]) перекладена як [[Індиферентний граф]], хоча хотіли [[Належний інтервальний граф]] (SashkoR0B0T)--> ([[Інтервальний граф|інтервальні графи]], утворені як [[Граф перетинів|графи перетинів]] сімейств інтервалів, де жоден інтервал не містить інший інтервал сімейства) не мають клешень, оскільки чотири таких інтервали не можуть перетинатися за схемою клешні.{{sfn|Faudree, Flandrin, Ryjáček|1997|p=89}}
* [[Веретено Мозера]]&nbsp;(граф, що має сім вершин та використовується для доведення нижньої межі [[Проблема Нельсона — Ердеша — Гадвігера|хроматичного числа площини]]) не має клешень.
* Графи деяких [[багатогранник]]ів і [[політоп]]ів не мають клешень. Сюди входять граф [[тетраедр]]а і взагалі будь-який [[симплекс]] (повний граф), граф [[октаедр]]а і, в загальному випадку, будь-який [[Гіпероктаедр|крос-політоп]] ([[Ізоморфізм графів|ізоморфний]] граф-ізоморфен, який утворюється завдяки видаленню досконалого парування з повного графу), граф правильного [[ікосаедр]]а<ref name="perfect"/>, і граф [[Шістнадцятикомірник|гексадекахорона]].
* [[Граф Шлефлі]], [[сильно регулярний граф]], що має 27 вершин, не має клешень<ref name="perfect"/>.

== Розпізнавання ==
Можна перевірити безпосередньо, що заданий граф з ''n'' вершинами і ''m'' ребрами не має клешень за час O(''n''<sup>4</sup>)) шляхом перевірки кожної четвірки вершин&nbsp;— чи не породжують вони клешню{{sfn|Faudree, Flandrin, Ryjáček|1997|p=132}}. Трохи ефективніше, але складніше, можна перевірити, чи не має граф клешень шляхом перевірки для кожної вершини графу, що доповнення графу сусідів вершини не містить трикутника. Граф містить трикутник в тому і тільки в тому випадку, якщо [[Куб (алгебра)|куб]] [[Матриця інцидентності|матриці інцидентності]] містить ненульовий діагональний елемент, так що пошук трикутника може бути здійснений за той же асимптотичний час, що і [[множення матриць]] ''n'' × ''n.''<ref>{{Стаття | автор = Alon Itai, Michael Rodeh|doi = 10.1137/0207033|mr = 0508603|випуск = 4| видання=[[SIAM Journal on Computing]]|сторінки=413—423|заголовок=Finding a minimum circuit in a graph|том= 7|рік = 1978}}</ref> Таким чином, при використанні [[Алгоритм Копперсміта-Вінограда|алгоритму Копперсміта—Винограда]], загальний час визначення, чи є у графу клешні, становить O(''n''<sup>3.376</sup>).

Клокс, Крач і Мюллер<ref>{{Стаття|автор=Ton Kloks, Dieter Kratsch, Haiko Müller |doi = 10.1016/S0020-0190(00)00047-8|mr = 1761552|випуск = 3—4|видання=Information Processing Letters| сторінки=115—121 | заглавие = Finding and counting small induced subgraphs efficiently| том = 74|рік= 2000}}</ref> звернули увагу на те, що в графі без клешень кожна вершина має максимум <math>2 \sqrt{m}</math> сусідів, в іншому випадку згідно з [[Теорема Турана|теоремою Турана]] околиця вершини не матиме достатнє число ребер, щоб сформувати додаток графу без трикутників. Це спостереження дозволяє перевірити сусідів з використанням згаданого раніше алгоритму швидкого добутку матриць за той же асимптотичний час <math>2\sqrt{m}*2\sqrt{m}</math>. Найгірший випадок цього алгоритму виникає, коли Ω(√''m'') вершин мають по Ω(√''m'') сусідів кожна, а решта вершин мають мало сусідів, у цьому випадку загальний час дорівнює (''m''<sup>3.376/2</sup>) = O(''m''<sup>1.688</sup>).

== Перерахування ==
Оскільки графи без клешень мають усі доповнення графів без трикутників, число графів без клешень з ''n'' вершинами росте як мінімум з тією ж швидкістю, що і число графів без трикутників, тобто, по експоненті від кореня з ''n''. Число зв'язкових графів без клешень з ''n'' ребрами для ''n'' = 1, 2, … складає:
: 1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, … {{OEIS|A022562}}.
Якщо графи незв'язні, їх число збільшується:
: 1, 2, 4, 10, 26, 85, 302, 1285, 6170, … {{OEIS|A086991}}.
Техніка Палмера, Ріда і Робінсона<ref>{{Статья
 | автор = Edgar M. Palmer, Ronald C. Read, Robert W. Robinson
 | doi = 10.1137/S0895480194274777
 | mr = 1972075
 | выпуск = 1
 | издание = [[SIAM Journal on Discrete Mathematics]]
 | страницы = 65—73
 | заглавие = Counting claw-free cubic graphs
 | url = http://www.cs.uga.edu/~rwr/publications/claw.pdf
 | том = 16
 | год = 2002}}</ref> дозволяє порахувати число [[Кубічний граф|кубічних графів]] без клешень дуже ефективно, що є незвичним для задач на [[перерахування графів]].

== Парування ==
[[Файл:Sumner claw-free matching.svg|thumb|240px|Доведення Самнера, що зв'язні графи без клешень парного порядку мають досконале парування: видалення двох суміжних вершин v і w, найбільш віддалених від u, залишає підграф зв'язковим, що дозволяє продовжити процес.]]
Самнер<ref>{{Стаття|автор = David P. Sumner |doi = 10.2307/2039666|mr = 0323648|видання= Proceedings of the American Mathematical Society| сторінки=8—12| заголовок=Graphs with 1-factors|том = 42|рік=1974|випуск = 1| видавництво = American Mathematical Society|jstor = 2039666}}</ref> і, незалежно, Лас Вергнас<ref>{{Стаття|автор = M. Las Vergnas|mr = 0412042|випуск = 2—3—4|видання = Cahiers du Centre d'Études de Recherche Opérationnelle|сторінки= 257—260| заголовок = A note on matchings in graphs|том = 17|рік= 1975}}</ref> довели, що будь-який [[зв'язний граф]] без клешень з парним числом вершин має [[Парування (теорія графів)|досконале парування]]{{sfn|Faudree, Flandrin, Ryjáček|1997|p=120—124}}. Тобто існує безліч ребер в графі так, що кожна вершина є кінцевою вершиною в точності одного ребра з парування. З цього випливає, що для реберних графів, що мають парне число ребер, можна розбити всі ребра на шляхи довжиною два. Досконалі парування можуть бути використані для ще однієї характеристики графів без клешень&nbsp;— це точно ті графи, в яких будь-який зв'язний породжений підграф парного порядку має досконале парування{{sfn|Faudree, Flandrin, Ryjáček|1997|p=120—124}}.

Доведення Самнера показує, що в будь-якому зв'язковому графі без клешень можна знайти пару сполучених вершин, видалення яких залишає граф зв'язковим. Для доведення цього Самнер знаходить пару вершин ''u'' і ''v'', які як можна більше віддалені один від одного, і вибирає ''w'' серед сусідів вершини ''v'', віддалену від ''u'' наскільки можливо. Як він показав, ні ''v'', ні ''w'' не можуть лежати на найкоротшому шляху від будь-якої іншої вершини до ''u'', так що видалення вершин ''v'' і ''w'' залишає граф зв'язковим. Послідовне видалення таких пар утворює досконале парування в графі без клешень.

Та ж сама ідея доведення працює і в загальнішому випадку: якщо u&nbsp;— будь-яка вершина, ''v''&nbsp;— будь-яка вершина, максимально віддалена від ''u'', і ''w''&nbsp;— будь-яка сусідня вершина для ''v'', максимально віддалена від ''u''. Тепер видалення ''v'' і ''w'' з графу не змінює відстаней до ''u''. Таким чином, процес формування парування шляхом знаходження та видалення пар vw, максимально віддалених від ''u'', може бути здійснений за лінійний час простим [[Двійкове дерево пошуку#Пошук|обходом]] дерева [[Пошук в ширину|пошуку вшир]], розпочатого з вершини ''u''. Хробак, Наор і Новик<ref>{{Стаття|автор = Marek Chrobak, Joseph Naor, Mark B. Novick|contribution = Using bounded degree spanning trees in the design of efficient algorithms on claw-free graphs|doi = 10.1007/3-540-51542-9_13|editor1-last = Dehne | editor1-first = F.|editor2-last = Sack | editor2-first = J.-R. | editor2-link = Jörg-Rüdiger Sack|editor3-last = Santoro | editor3-first = N.|location = Berlin|сторінки=147—162|видавництво = Springer|series = Lecture Notes in Comput. Sci|заголовок={{iw|Algorithms and Data Structures Symposium|Algorithms and Data Structures: Workshop WADS '89, Ottawa, Canada, August 1989, Proceedings|en|Algorithms and Data Structures Symposium}}|том = 382|рік= 1989}}</ref> дали інший лінійний за часом алгоритм, заснований на [[Пошук у глибину|пошуку вглиб]], а також ефективні [[Паралельний алгоритм|паралельні алгоритми]] для тієї ж задачі. Фаудрі, Фландрін и Ріяче{{sfn|Faudree, Flandrin, Ryjáček|1997}} отримали кілька схожих результатів, зокрема:
 
# (''r'' − 1)-зв'язний граф, що не містить ''K''<sub>1,''r''</sub>  підграфів непарного порядку, має досконалі парування для будь-якого ''r'' ≥ 2;
# графи непарного порядку без клешень з максимум однією вершиною степені один можуть бути поділені на один непарний цикл і парування;
# для будь-якого ''k'', не меншого за половину мінімальної степені графу без клешень, у якому або ''k'', або число вершин парно, граф має ''k''-фактор;
# якщо граф без клешень є (2''k'' + 1)-зв'язним, то будь-які ''k''-реберні парування можуть бути розширені до досконалого парування.

== Незалежні множини ==
[[Файл:Claw-free augmenting path.svg|thumb|220px|Немаксимальна незалежна множина (дві фіолетові вершини) і доповнюючий шлях.]]
[[Задача про незалежну множину|Незалежна множина]] в реберному графі відповідає паруванню у вихідному графі, тобто набору ребер, в якому ніякі два ребра не мають спільних точок. Як показав Едмондс<ref>{{Стаття|doi = 10.4153/CJM-1965-045-4|автор = Jack Edmonds|mr=0177907|видання=Canadian J. Math| сторінки=449—467|випуск=0|заголовок= Paths, Trees and Flowers|том = 17|рік=1965}}</ref>, максимальне парування в будь-якому графі можна знайти за поліноміальний час; Сбіхі<ref>{{Стаття|автор = Najiba Sbihi|doi= 10.1016/0012-365X(90)90287-R|mr=553650|випуск=1| видання=Discrete Mathematics|сторінки= 53—76| заголовок= Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile|том= 29|рік= 1980}} {{ref-fr}}</ref> розширив цей алгоритм так, що новий алгоритм знаходить максимальну незалежну множину в будь-якому графі без клешень{{sfn|Faudree, Flandrin, Ryjáček|1997|p=133—134}}. Мінті<ref>{{Стаття|автор = George J. Minty|doi = 10.1016/0095-8956(80)90074-X|mr=579076|випуск=3| видання=Journal of Combinatorial Theory. Series B| сторінки=284—304|заголовок=On maximal independent sets of vertices in claw-free graphs|том=28|рік=1980}} {{ref-en}}</ref>, виправлений Накамурою і Тамурою,<ref>{{Стаття|автор=Daishin Nakamura, Akihisa Tamura|випуск=2|видання=Journal of the Operations Research Society of Japan|сторінки=194—204|заголовок=A revision of Minty's algorithm for finding a maximum weighted stable set of a claw-free graph|url=http://www.kurims.kyoto-u.ac.jp/preprint/file/RIMS1261.ps.gz|том=44|рік=2001|accessdate=30 жовтня 2015|archivedate=3 березня 2016|archiveurl=https://web.archive.org/web/20160303175540/http://www.kurims.kyoto-u.ac.jp/preprint/file/RIMS1261.ps.gz}} {{ref-en}}</ref> дав інше розширення алгоритмів Едмонда для графів без клешень, перетворюючого задачу на пошук парування у допоміжному графі, отриманого із вихідного графу без клешень. Підхід Мінті може бути використаний для вирішення за поліноміальний час більш загальної задачі знаходження незалежної множини максимальної ваги. Існує узагальнення цих результатів на широкий клас графів.{{sfn|Faudree, Flandrin, Ryjáček|1997|p=133—134}}

Як зауважив Сбіхі, якщо <math>I</math>&nbsp;— незалежна множина в графі без клешень, то будь-яка вершина графу може мати максимум дві сусідні вершини з <math>I</math>&nbsp;— три сусідні вершини утворили б вже саму клешню. Сбіхі називає вершину насиченою, якщо вона має дві сусідні вершини з <math>I</math>, і ненасиченою, якщо вона не належить, і, в той же час, має менше двох сусідів з <math>I</math>. Зі спостереження Сбіхі випливає, що, якщо <math>I</math> і <math>J</math> є незалежні множини, то граф, породжений <math>I \cup J</math>, повинен мати ступінь не вище другого. Таким чином, він є об'єднанням шляхів і циклів. Зокрема, якщо <math>I</math>&nbsp;— не максимальна незалежна множина, вона відрізняється від будь-якої максимальної незалежної множини циклами і ''поповнюючими шляхами'', тобто шляхами, в яких вершини з <math>I</math> і не з <math>I</math> чергуються, і у яких обидві кінцеві вершини не насичені. Симетрична різниця графів <math>I</math> і поповнюючого шляха є максимальна незалежна множина (симетрична різниця графів H і G, що мають один і той же набір вершин V&nbsp;— це граф з тим же набором вершин V, що містить ребра G і H, але не містить загальних ребер, що належать як G, так і H). Алгоритм Сбіхі послідовно збільшує розмір незалежної множини шляхом знаходження поповнюючих шляхів, доки такі можна знайти.

Знаходження поповнюючого шляху є складним завданням, оскільки поширення шляху може і не існувати, якщо він містить ребро між двома вершинами, що не належать <math>I</math>. На щастя, це може статися тільки в двох випадках: дві суміжні вершини можуть бути кінцевими вершинами шляху, або між ними лежить одна вершина, суміжна обом. Будь-яка інша суміжна вершина призведе до клешні. Суміжних кінцевих вершин можна позбутися, тимчасово видаляючи всі суміжні ''v'' вершини перед пошуком поповнюючого шляху, початківця в ''v''. Якщо знайдений шлях не буде входити у вершину ''v'', можна видалити його з графу до кінця алгоритму. Після такої редукції графу завдання може бути описано в термінах {{Нп|Граф-перемикач|графу-перемикача|en|Skew-symmetric graph}}, хоча Сбіхі і не користувався цією термінологією. Граф-перемикач&nbsp;— це ненаправлений граф, в якому дуги будь-якої вершини розділені на дві групи, і будь-який шлях, що проходить через вершину, зобов'язаний містити ребра з обох груп. Можна побудувати граф-перемикач на множині насичених і ненасичених вершин графу без клешень, ребра якого з'єднують вершини, якщо вони не є суміжними у вихідному графі, і існує шлях довжини 2 між ними, що проходить через вершину з ''I''. Дві множини ребер в кожній вершині утворюються двома вершинами ''I'', через які ці шляхи, довжиною 2, проходять. Шлях у графі-перемикачі між двома ненасиченими вершинами відповідає поповнюючому шляху у вихідному графі. Граф-перемикач має квадратичну складність, і шлях у ньому може бути знайдений за лінійний час, а за весь час роботи алгоритму можуть знадобитися O(''n'') поповнюючих шляхів, які необхідно знайти. Таким чином, алгоритм Сбіхі вимагає O(''n''<sup>3</sup>) часу роботи.

== Розфарбовування, кліки, і домінування ==
[[Досконалий граф]]&nbsp;— це граф, в якому [[хроматичне число]] дорівнює розміру максимальної [[Кліка (теорія графів)|кліки]], і в якому ця рівність зберігається у всіх породжених підграфах. Відомо (зі [[Сильна теорема про досконалі графи|сильної теореми про досконалі графи]]), що досконалі графи можуть бути охарактеризовані як графи, що не мають непарних циклів чи доповнень непарним циклам (так звані ''непарні діри'')  як індукованих підграфів<ref name="perfect">{{Стаття|автор = [[Марія Чудновська|Maria Chudnovsky]], Neil Robertson, Paul Seymour, Robin Thomas|doi = 10.4007/annals.2006.164.51|journal = [[Annals of Mathematics]]|страницы = 51—229|заглавие = The strong perfect graph theorem|випуск = 1|url = http://people.math.gatech.edu/~thomas/PAP/spgc.pdf|том = 164|рік = 2006|title = Архівована копія|accessdate = 30 жовтня 2015|archivedate = 11 жовтня 2015|archiveurl = https://web.archive.org/web/20151011212920/http://people.math.gatech.edu/~thomas/PAP/spgc.pdf}} {{ref-en}}</ref>. Проте багато років цей факт залишався гіпотезою, доведеною тільки для спеціальних підкласів графів. Одним з таких підкласів було сімейство графів без клешень&nbsp;— кілька авторів виявили, що графи без клешень і без непарних циклів і дірок досконалі. Досконалість графу без клешень може бути перевірена за поліноміальний час. У досконалому графі без клешень околиця будь-якої вершини утворює доповнення [[Двочастковий граф|двочасткового графу]]. Можна [[Хроматичне число|розфарбувати]] досконалий граф без клешень або знайти в ньому максимальну кліку за поліноміальний час{{sfn|Faudree, Flandrin, Ryjáček|1997|p=135—136}}.

Якщо граф без клешень не досконалий, завдання пошуку максимальної кліки стає NP-задачею{{sfn|Faudree, Flandrin, Ryjáček|1997|p=132}}. Задача знаходження оптимального [[Розфарбовування графів|розфарбування]] такого графу також є NP-задачею, оскільки (через реберний граф) ця задача узагальнює NP-завдання обчислення хроматичного числа графу{{sfn|Faudree, Flandrin, Ryjáček|1997|p=132}}. З тієї ж причини NP-завданням є пошук алгоритму розфарбовування, гарантована ефективність якого краще, ніж 4/3. Однак гарантовану ефективність, рівну двом, можна отримати в алгоритмі [[Жадібне розфарбовування|жадібного розфарбовування]], оскільки хроматичне число графу без клешень більше, ніж половина його максимального ступеня.

Хоча не всі графи без клешень досконалі, графи без клешень задовільняють іншій властивості, пов'язаній з досконалістю. Граф називається досконалим графом домінування, якщо він має мінімальну [[Домінівна множина|домінуючу множину]], що є незалежною множиною вершин, і якщо тією ж властивістю володіють всі породжені підграфи. Графи без клешень володіють цією властивістю. Щоб показати це, уявимо, що ''D''&nbsp;— домінуюча множина в графі без клешень, і нехай ''v'' і ''w''&nbsp;— дві сполучені вершини ''D''. Тоді безліч вершин, домінованих вершиною ''v'', але не ''w'', повинно бути [[Кліка (теорія графів)|кліком]] (в іншому випадку v виявиться центром клешні). Якщо кожна вершина цієї кліка вже домінується принаймні одним членом множини ''D'', то v може бути видалена з породженням меншої незалежної домінуючої множини. В іншому ж випадку v можна замінити однією з недомінуючих вершин з кліка, породжуючи домінуючу множину з меншим числом суміжних вершин. Повторюючи ці заміни, ми досягнемо домінуючої множини, що не перевершує ''D'', так що, якщо початкове ''D''&nbsp;— мінімальна домінуюча множина, процес закінчиться створенням рівної за розміром незалежної домінуючої множини{{sfn|Faudree, Flandrin, Ryjáček|1997|p=124—125}}.

Незважаючи на властивість досконалого домінування, визначення розміру мінімальної домінуючої множини в графі без клешень є NP-завданням{{sfn|Faudree, Flandrin, Ryjáček|1997|p=132}}. Однак в контраст з більш загальними класами графів, пошук мінімальної домінуючої множини в графі без клешень володіє {{Нп|Параметрична складність|параметичною складністю з фіксованими параметрами|en|Parameterized complexity}}&nbsp;— завдання може бути вирішено за час, поліноміально залежний від розміру графу і експоненціально від розміру домінуючої множини<ref>{{Статья
 | автор = Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk
 | eprint = 1011.6239 
 | заглавие = Dominating set is fixed parameter tractable in claw-free graphs
 | год = 2010
}}</ref><ref name="Hermlin">{{Статья
 | автор = Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, Gerhard Woeginger
 | eprint = 1012.0012 
 | заглавие = Domination when the stars are out
 | год = 2010
}}</ref>.

== Структура ==
У серії статей Чудновська і Сеймур<ref>{{Статья
 | автор = [[Марія Чудновська|Maria Chudnovsky]], Paul Seymour
 | contribution = The structure of claw-free graphs
 | mr = 2187738
 | location = Cambridge
 | страницы = 153—171
 | издательство = Cambridge Univ. Press
 | series = London Math. Soc. Lecture Note Ser
 | заглавие = Surveys in combinatorics 2005
год | url = http://www.math.princeton.edu/~mchudnov/claws_survey.pdf
 | том = 327
 | год = 2005}}</ref> довели структурну теорію графів без клешень, аналогічну для сімейств мінорно-замкнутих графів, доведену Робертсоном і Сеймуром, і структурній теорії для досконалих графів, яку Чудновська, Сеймур та їх співавтори використовували для доведення теореми про строго досконалий граф<ref name="perfect"/>. Теорія занадто складна, але можливо описати декілька її наслідків. По-перше, для спеціального підкласу графів без клешень, який вони назвали ''квазіреберні графи'' (або локально квазідвудольні графи), вони стверджують, що кожен такий граф має одну з двох форм:
# ''Нечіткий коловий інтервальний граф''&nbsp;— клас графів, які геометрично можна представити як точки і дуги на колі.
# Граф, який можна побудувати з мультиграфу шляхом заміни кожного ребра ''нечітким лінійним інтервальним графом''. Це узагальнює конструкцію реберних графів, в яких кожне ребро мультиграфу замінюється вершиною. Нечіткі лінійні інтервальні графи будуються так само, як і нечіткі колові інтервальні графи, тільки на відрізку, а не на колі.

Чудновська і Сеймур класифікували довільні зв'язні графи без клешень наступним чином:
# Шість специфічних графів без клешень. Три з них є реберними графами, деякі&nbsp;— графи дуг кола і останні&nbsp;— породжені підграфи [[ікосаедр]]а. Решта три вимагають додаткових визначень.
# Графи, утворені чотирма простими способами з менших графів без клешень.
# ''Антипризматичні графи''&nbsp;— клас [[Щільний граф|щільних графів]], визначаються як графи без клешень, в яких будь-які чотири вершини породжують підграф з мінімум двома ребрами.
Більша частина їх роботи з класифікації присвячена аналізу антипризматичних графів. [[Граф Шлефлі]], [[сильно регулярний граф]] без клешень з параметрами srg (27,16,10,8), відіграє важливу роль у цій частині аналізу. Ця структурна теорія призвела до нового просування в [[Комбінаторика багатогранників|комбінаториці багатогранників]] і нових кордонів хроматичних чисел графів без клешень<ref name=" perfect"/>, а також до нових алгоритмів параметричної складності з фіксованими параметрами для домінуючих множин в графах без клешень<ref name="Hermlin"/>.

== Посилання ==
* [https://web.archive.org/web/20090803213650/http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_62.html Claw-free graphs], інформаційна система на Graph Class Inclusions
* {{mathworld|title=Claw-Free Graph|urlname=Claw-FreeGraph|author=Mugan, Jonathan William; [[Eric W. Weisstein|Weisstein, Eric W.]]}}

== Джерела ==
{{reflist|3}}

== Література ==
* {{Стаття
 | автор = Ralph Faudree, Evelyne Flandrin, Zdeněk Ryjáček
 | doi = 10.1016/S0012-365X(96)00045-3
 | mr = 1432221
 | випуск = 1—3
 | видання = Discrete Mathematics
 | сторінки = 87—147
 | заглавие= Claw-free graphs — A survey
 | том = 164
 | рік= 1997
 | ref = Faudree, Flandrin, Ryjáček
}}

[[Категорія:Теорія графів]]
[[Категорія:Види графів]]
[[Категорія:Парування]]