Podmínky na 4-cykly pro 3-vybíravost rovinných grafů bez trojůhelníků

Abstrakt

Ukazujeme, že když rovinný graf bez trojůhelníků není 3-vybíravý, pak existuje 4-cyklus, který sdílý s jiným 4-cyklem či 5-cyklem právě jednu hranu. Toto vylepšuje vylepšuje výsledek C.

Thomassena [C. Thomassen, J.

Combin. Theory Ser.

B, 64 (1995), pp. 101-107], že každý graf bez trojůhelníků a bez 4-cyklů je 3-vybíravý.

Klíčová slova

• rovynné grafy
• grafy bez trojúhelníků
• barevnost
• vybíravost