Přeplněný graf - Overfull graph

v teorie grafů, an přeplněný graf je graf, jehož velikost je větší než součin jeho maxima stupeň a polovina jeho objednat s podlahou, tj. ${displaystyle | E |> Delta (G) lfloor | V | / 2floor}$ kde ${displaystyle | E |}$ je velikost G, ${displaystyle displaystyle Delta (G)}$ je maximální stupeň G, a ${displaystyle | V |}$ je řád G. Koncept přeplněný podgraf, přeplněný graf, který je a podgraf, okamžitě následuje. Vyžaduje alternativní přísnější definice příliš velkého podgrafu S grafu G. ${displaystyle displaystyle Delta (G) = Delta (S)}$.

Vlastnosti

Několik vlastností přeplněných grafů:

1. Přeplněné grafy jsou lichého pořadí.
2. Přeplněné grafy jsou třída 2. To znamená, že vyžadují minimálně Δ + 1 barvy v jakékoli zbarvení hran.
3. Graf G, s přeplněným podgrafem S takhle ${displaystyle displaystyle Delta (G) = Delta (S)}$, je třídy 2.

Přehnané dohady

V roce 1986 Amanda Chetwynd a Anthony Hilton navrhl následující domněnku, která je nyní známá jako přehnaná domněnka.^[1]

Graf G s ${displaystyle Delta (G) geq n / 3}$ je třída 2 právě tehdy, pokud má přeplněný podgraf S takový, že ${displaystyle displaystyle Delta (G) = Delta (S)}$.

Tato domněnka, pokud je pravdivá, by měla řadu důsledků v teorii grafů, včetně 1-faktorizační domněnka.^[2]

Algoritmy

Pro grafy, ve kterých ${displaystyle Delta geq {frac {n} {3}}}$, jsou maximálně tři indukovaný přeplněný podgraf, a je možné najít přeplněný podgraf v polynomiální čas. Když ${displaystyle Delta geq {frac {n} {2}}}$existuje nanejvýš jeden indukovaný přeplněný podgraf a je možné jej najít v lineárním čase.^[3]

Reference