Zakázaná indukovaná cesta
Úloha číslo: 3577
Najděte všechny grafy, které neobsahují indukovanou cestu délky \(2\).
Řešení
Podobně jako v předchozí úloze se lze omezit na komponenty souvislosti.
Úplné grafy neobsahují cestu délky \(2\) neboli graf \(P_3\) indukovaně, protože každá trojice vrcholů indukuje \(K_3\) a nikoli \(P_3\).
Jiné komponenty než úplné být nemohou. Není-li souvislý graf úplný, obsahuje dva vrcholy \(u\) a \(v\) ve vzdálenosti alespoň dva. Potom první tři vrcholy z nejkratší cesty z \(u\) do \(v\) určují indukovaný \(P_3\).
Odpověď
Grafy bez indukované \(P_3\) jsou disjunktní sjednocení úplných grafů.