Idealny wykres liniowy
W teorii grafów graf liniowo doskonały to graf , którego wykres liniowy jest grafem doskonałym . Równoważnie, są to wykresy, w których każdy cykl prosty o nieparzystej długości jest trójkątem.
Graf jest idealnie liniowy wtedy i tylko wtedy, gdy każdy z jego dwupołączonych składników jest grafem dwudzielnym , pełnym grafem K 4 lub trójkątną księgą K 1,1, n . Ponieważ wszystkie te trzy typy składowych dwupołączonych same w sobie są doskonałymi wykresami, każdy doskonały graf liniowy sam w sobie jest doskonały. Z podobnego rozumowania wynika, że każdy graf doskonały liniowo jest grafem parzystości , grafem Meyniela i grafem doskonale uporządkowanym .
Wykresy liniowe uogólniają grafy dwudzielne i dzielą z nimi te właściwości, że maksymalne dopasowanie i minimalne pokrycie wierzchołków mają ten sam rozmiar, a indeks chromatyczny jest równy maksymalnemu stopniowi .
Zobacz też
- Wykres uduszony , wykres, w którym każdy cykl peryferyjny jest trójkątem