| Meno: | Matúš
|
|---|
| Priezvisko: | Zubčák
|
|---|
| Názov: | Hranové farbenia regulárnych grafov
|
|---|
| Vedúci: | doc. RNDr. Edita Mačajová, PhD.
|
|---|
| Rok: | 2024
|
|---|
| Kľúčové slová: | snark, Kászonyiho funkcia, rotačné binárne snarky, 4-regulárne grafy, regulárne hranové farbenia
|
|---|
| Abstrakt: | V našej práci skúmame Kászonyiho funkciu a maximálne počty hranových 4-farbení
na jednoduchých 4-regulárnych grafoch. V teórii grafov sú hranovo 3-nezafarbiteľné kubické grafy predmetom intenzívneho výskumu, pretože mnohé známe hypotézy v teórii grafov je postačujúce dokázať pre kubické grafy a pre hranovo 3-zafarbiteľné kubické grafy sú už tieto hypotézy dokázané. Kászonyiho funkcia ponúka isté charakteristiky pre hranovo 3-nezafarbiteľné kubické grafy. Presnejšie, Kászonyiho funkcia ψ(G, e) vyjadruje počet rôznych hranových 3-farbení kubického grafu G po potlačení hrany e, pričom potlačenie hrany je odobratie hrany a vyhladenie incidentných vrcholov druhého stupňa. V práci určíme hodnotu Kászonyiho funkcie ψ(G, e) pre ľubovoľnú hranu e každého grafu z nekonečnej triedy rotačných binárnych snarkov. V druhej časti našej práce pomocou výpočtovej techniky určíme počet hranových 4-farbení na 4-regulárnych
grafoch do 18 vrcholov. Ako MAXc(n) definujeme funkciu, ktorá určuje maximálny počet hranových 4-farbení na jednoduchých 4-regulárnych grafoch v závislosti od počtu vrcholov n. Na základe pozorovania súvislostí medzi grafmi s maximálnym počtom 4-farbení na 4-regulárnych grafoch do 18 vrcholov skonštruujeme nekonečnú triedu 4-regulárnych grafov, ktorá ponúka kvalitný netriviálny dolný odhad funkcie MAXc(n). Súčasťou práce je aj dôkaz počtu hranových 4-farbení pre ľubovoľný graf z tejto nekonečnej triedy grafov.
|
|---|