| Abstrakt: | Majme jednoduchý neorientovaný graf $G$ a všetky jeho vrcholové farbenia $\mathcal{C}$. Množina vrcholov grafu farbení je totožná s množinou farbení $\mathcal{C}$. Hrany grafu farbení závisia od toho, akú operáciu na farbeniach si zvolíme. Najčastejšie sa skúmajú 2 typy: výmena farieb vrcholov na komponente grafu indukovaného dvomi farbami (Kempe-prepnutie) a zmena farby jedného vrchola. V práci sa zaoberáme prvým typom na hranových grafoch. Kempe-ekvivalentné farbenia sú také, že medzi vrcholmi týchto farbení existuje cesta v grafe farbení. Ak sú všetky farbenia grafu navzájom Kempe-ekvivalentné, hovoríme, že graf je Kempe-ekvivalentný. V práci ukážeme vzťah medzi Kempe-ekvivalenciou a hranovou $k$-vyberateľnosťou grafu. Dokážeme niektoré vlastnosti grafu farbení pre hranové grafy, najmä že izomorfné farbenia sú Kempe-ekvivalentné. Dokážeme, že ak bipartitný graf $G$ nie je Kempe-ekvivalentný, potom akýkoľvek bipartitný graf, ktorý obsahuje podgraf izomorfný s $G$, tiež nie je Kempe-ekvivalentný. Tento poznatok v práci využívame na analýzu Kempe-ekvivalencie subkubických grafov s chromatickým indexom nanajvýš $3$. Práve na tieto grafy je možné použit poznatky o $k$-vyberateľnosti grafu. Zavedieme operáciu na subkubických grafoch, ktorá zachováva Kempe-ekvivalenciu a ukážeme nekonečnú množinu blokov, ktorými je možné grafy rozširovať.
|
|---|