Barvení rovinných grafů vyhýbající se jednobarevným podgrafům: stromy a cesty to dělají složitým

Abstrakt

Studujeme otázku barvení rovinných grafů tak, aby se v žádné barvě nevyskytl zakázaný podgraf. Ukazujeme, že 2-barvení je NP-úplné v případě, že zakázaným grafem je strom s alespoň dvěma hranami, a polynomiální jinak, zatímco 3-barvení je NP-úplné v případě, že zakázaný graf je cesta s alespoň jednou hranou, a polynomiální jinak.

Klíčová slova

• Planar
• graph
• coloring
• avoiding
• monochromatic
• subgraphs
• Trees
• paths
• difficult