Abstrakt
Motivováni satelitním komunikačním problémem uvažujeme zobecněný problém barvení jednotkových diskových grafů. Barvení je k-nepravé jestliže nanejvýš k sousedů každého vrcholu má stejnou barvu jako tento vrchol. k-nepravé chromatické číslo chi(k)(G) je nejmenší počet barev potřebných ke k-nepravému obarvení grafu G.
Hlavní příspěvek tohoto článku je analýza složitosti výpočtu chi(k) pro třídu jednotkových diskových grafů a jiných podobných tříd. Dokážeme NP-úplnost a odvodíme různé aproximační výsledky.
Nicméně ještě řada souvisejících problémů zůstává otevřená.