Barion Pixel Kromatikus szám alsó és felső becslése | mateking
 

Kromatikus szám alsó és felső becslése

\( \omega(G) \leq \chi(G) \leq \Delta(G) + 1 \)

ahol $\omega(G)$ a gráf klikkszáma, $\chi(G)$ a kromatikus száma és $\Delta(G)$ a maximális fokszáma.

Ezt a képletet még az alábbi kurzusainkban is megtalálod:
Diszkrét matematika / Kromatikus szám, klikk, perfekt gráfok / Mohó színezés, becslés a kromatikus számra
Bevezetés a számításelméletbe 2 / Kromatikus szám, klikk, perfekt gráfok / Mohó színezés, becslés a kromatikus számra
Számítástudomány alapjai / Kromatikus szám, klikk, perfekt gráfok / A mohó színezés, becslés a kromatikus számra
Számítástudomány / Kromatikus szám, klikk, perfekt gráfok / A mohó színezés, becslés a kromatikus számra

Egy gráf kromatikus száma a gráf klikkszáma és a gráf maximális fokszáma plusz egy közé esik.

Kapcsolatfelvétel
Rólunk
Tartalomjegyzék
GYIK Általános szerződési feltételek Adatkezelési tájékoztató Felhasználás oktatási célra

© Minden jog fenntartva!

Az oldalon található tartalmak részének vagy egészének másolása, elektronikus úton történő tárolása vagy továbbítása, harmadik fél számára nyújtott oktatási célra való hasznosítása kizárólag az üzemeltető írásos engedélyével történhet. Ennek hiányában a felsorolt tevékenységek űzése büntetést von maga után!