Subchromatický index grafů

Abstrakt

Ukzaujeme, že rozpoznání grafů subchromatického indexu 2 nebo 3 je NP-úplné. Dále předkládáme polynomiální algoritmus pro grafy omezeného stromového zdvihu.

Klíčová slova

• Subchromatický index
• teorie grafů