Perfect Graph Recognition and Coloring.

Badania nad grafami doskonałymi trwają nieprzerwanie od ich wprowadzenia w 1961 roku. Dopiero w roku 2001 została udowodniona słynna hipoteza o grafach doskonałych, a w roku 2005 opublikowany został pierwszy wielomianowy algorytm rozpoznający grafy doskonałe. Od 1988 roku znany jest algorytm kolorujący grafy doskonałe, ale korzysta on z metody elipsoidalnej, która jest uznawana za skomplikowaną i niepraktyczną. W 2018 roku opublikowany został kombinatoryczny algorytm kolorujący grafy doskonałe niezawierające kwadratów.Rozdział 1 zawiera podstawowe definicje teorii grafów. Rozdział 2 zawiera wprowadzenie do grafów doskonałych, grafów Berge'a, krótki opis twierdzenia o grafach doskonałych oraz algorytm rozpoznawania grafów doskonałych. Rozdział 3 stanowi opis metody elipsoidalnej kolorowania grafów doskonałych. W rozdziale 4 omawiana jest implementacja wspomnianych algorytmów, wraz z informacjami o wprowadzonych optymalizacjach i zrównolegleniu. Appendix A jest krótkim omówieniem algorytmu kolorowania grafów doskonałych bez kwadratów.

Perfect graphs are a subject of intense study since their introduction in 1961. Only in 2001 the famous perfect graph conjecture was proven to be true and in 2005 a polynomial method of determining if a graph is perfect was found. Since 1988 an algorithm is known for coloring perfect graphs, but it uses an ellipsoid method which is said to be complicated and impractical. As recently as in 2018 a polynomial algorithm that uses a combinatorial approach for coloring perfect graphs without squares was published.We begin with basic definitions in Chapter 1. In Chapter 2 we introduce perfect graphs and Berge graphs, give an overview of the strong perfect graph theorem and talk about an algorithm for polynomial perfect graph recognition. Chapter 3 is a study of the ellipsoid method of coloring perfect graphs. In Chapter 4 we present our implementation of algorithms from Chapters 2 and 3, along with notes on optimization and parallelisation. Appendix A is a overview of the recent algorithm for coloring square-free perfect graphs.