Chromatic Graph Theory - 9781584888000

Począwszy od powstania problemu czterech kolorów w 1852 roku, dziedzina kolorowania grafów stała się jedną z najpopularniejszych dziedzin teorii grafów. Wprowadzając teorię grafów z motywem kolorowania, teoria grafów chromatycznych bada powiązania między głównymi tematami teorii grafów i kolorowaniem grafów, a także pojawiającymi się tematami. W tej samodzielnej książce w pierwszej kolejności przedstawiono różne podstawy teorii grafów wykraczające poza kolorowanie grafów, w tym podstawową terminologię i wyniki, drzewa i spójność, wykresy Eulera i Hamiltona, dopasowania i faktoryzację oraz osadzanie grafów. Pozostała część tekstu dotyczy wyłącznie kolorowania wykresów. Obejmuje kolorowanie wierzchołków i granice liczby chromatycznej, kolorowanie wierzchołków wykresów osadzonych na powierzchniach oraz różne ograniczone kolorowanie wierzchołków. Autorzy opisują także kolorowanie krawędzi, monochromatyczne i tęczowe kolorowanie krawędzi, pełne kolorowanie wierzchołków, kilka wyróżniających kolorowań wierzchołków i krawędzi oraz wiele kolorowań wierzchołków związanych z odległością. Tekst ten, zawierający dyskusje historyczne, stosowane i algorytmiczne, stanowi solidne wprowadzenie do jednego z najpopularniejszych obszarów teorii grafów.