| Abstrakt: | Jednoznačne hranovo 3-zafarbiteľné kubické grafy sú predmetom
skúmania už desaťročia. Vďaka tomu v tejto oblasti ostali najmä
problémy, o ktorých sa domnievame, že sú ťažké. Myslíme si,
že výsledky týkajúce sa grafov, ktoré majú namiesto jedného
dve farbenia môžu priniesť nový pohľad aj na problémy
súvisiace s jednoznačnou hranovou 3-zafarbiteľnosťou.
V tejto práci skúmame kubické grafy s malým počtom hranových
3-farbení. Prezentujeme konštrukcie nekonečných tried
takýchto grafov s cyklickou súvislosťou 4 a obvodom 4 a 5.
O grafoch z týchto tried dokazujeme, že skutočne majú
práve 2 hranové 3-farbenia. Konštrukcie zakladáme na spájaní
izochromatického Petersenovho 4-pólu s inými kubickými 4-pólmi.
V práci opisujeme aj graf, ktorý má spomedzi grafov
do 26 vrcholov ako jediný obvod 6 a práve 2 hranové 3-farbenia.
Okrem toho opisujeme ďalšie malé grafy s práve 2 hranovými 3-farbeniami,
ktoré sú medzi skupinou grafov s danou vlastnosťou vzácne.
|
|---|