1-2-3 Conjecture

A 1-2-3 conjecture is a conjecture formulated in 2004 by Karoński, Łuczak and Thomason. It states that every graph devoid of K_2 as a component can be weighed properly by the set {1,2,3}.In this thesis we first follow the best results on the path to proving the conjecture in its original statement. We explain in detail how thealgorithmic proof for the set {1,2,3,4,5} of Kalkowski, Karoński and Pfender proceeds and add some additional insight into the presented method.In the second part of the thesis we generalise the result of Dudek and Wajc about the NP-hardness of the problem of properly weighing a graph by the set {1,2}.

Hipoteza 1-2-3 to hipoteza sformułowana w roku 2004 przez Karońskiego, Łuczaka i Thomasona. Mówi ona, że każdy graf bez kliki K_2 może być zważony poprawnie przez zbiór {1,2,3}.W pierwszej części pracy przedstawiamy kolejne najlepsze wyniki na ścieżce do udowodnienia tej hipotezy w jej oryginalnym sformułowaniu.Następnie wyjaśniamy w szczegółach algorytmiczny dowód dla zbioru {1,2,3,4,5} przedstawiony przez Kalkowskiego, Karońskiego i Pfendera i prezentujemy kilka spostrzeżeń dotyczących przedstawionej metody.W drugiej części pracy uogólniamy wynik Dudka i Wajca dotyczący NP-trudności problemu poprawnego zważenie grafu za pomocą wag {1,2}.