Fano coloring of cubic graphs

V diplomskem delu se ukvarjamo s problemom Fano barvanja kubičnih grafov, ki predstavlja zanimivo povezavo med barvanjem povezav, teorijo pretokov in Steinerjevimi trojnimi sistemi. Najprej opredelimo temeljne pojme teorije grafov, pri čemer se osredotočimo na kubične grafe, popolna prirejanja in snarke, ter povzamemo klasične rezultate glede Taitovo barvanja. Fanojevo ravnino opišemo kot najmanjši netrivialni Steinerjev trojni sistem in razložimo njene značilnosti, ki omogočajo določitev Fano barvanja. V osrednjem delu naloge obravnavamo znane rezultate o Fano barvanju kubičnih grafov brez mostov. Predstavimo zgornje meje za najmanjše število premic Fanojeve ravnine, potrebnih za obarvanje, ter poudarimo ključne odprte domneve, kot sta domneva o štirih premicah in Fulkersonova domneva o šestih popolnih podmnožicah. Razpravo obogatimo s konkretnimi primeri, pri čemer posebej izpostavimo Petersenov graf.