| Meno: | Tatiana |
|---|---|
| Priezvisko: | Husárová |
| Názov: | Farbenia hranových grafov kubických grafov |
| Vedúci: | doc. RNDr. Edita Máčajová, PhD. |
| Rok: | 2025 |
| Kľúčové slová: | hranové farbenie, kubický graf, hranový graf |
| Abstrakt: | V našej práci sme sa sústredili na hranové H-farbenia 4-regulárnych grafov pre H grafy na troch vrcholoch, ktoré uviedli K. Ozeki a A. A. Malnegro v práci H-colorings for 4-regular graphs. Venovali sme sa konkrétne A-farbeniam a X-farbeniam hranových grafov kubických grafov a analyzovali sme grafy, ktoré majú jedno z týchto farbení, ale nie druhé. Na skúmanie existencie H-farbení v grafoch sme využili SAT-solver a optimalizované formuly. Ozeki a Malnegro vyslovili hypotézu, že každý hranový graf kubického bezmostového grafu má zároveň A- aj X-farbenie. Táto hypotéza bola vyvrátená v práci A note on X-coloring and A-coloring 4-regular graphs, kde autor našiel konečnú množinu kontrapríkladov. My sme na základe našich pozorovaní skonštruovali nekonečnú triedu bezmostových kubických grafov, o ktorej sme dokázali, že sú taktiež protipríkladmi proti tejto hypotéze. V závere sme sa zamerali na nové možné H grafy na štyroch a piatich vrcholoch pre 4-regulárne grafy. Preskúmali sme ich vzájomné vzťahy v kontexte H-farbení a našli sme grafy v jednotlivých prienikoch týchto farbení. |
Súbory diplomovej práce:
| husarova-dipl.pdf |
Súbory prezentácie na obhajobe: