Neduhové barvení 3-, 4- a 5-souvislých grafů

Abstrakt

Nalezneme horní odhad na nutný počet barev v neduhovém barvení rovinných 3-, 4- a 5-souvislých grafů. Naše odhady jsou optimální pro 3- a 4-souvislé grafy.

Klíčová slova

• neduhové barvení
• rovinné grafy