Note on coloring of double disk graphs

Autor: Martina Mockovčiaková, Borut Lužar, Jaka Kranjc, Roman Soták
Rok vydání: 2014
Předmět:
Zdroj: Journal of Global Optimization. 60:793-799
ISSN: 1573-2916
0925-5001
DOI: 10.1007/s10898-014-0221-z
Popis: The coloring of disk graphs is motivated by the frequency assignment problem. In 1998, Malesinska et al. introduced double disk graphs as their generalization. They showed that the chromatic number of a double disk graph $$G$$ G is at most $$33\,\omega (G) - 35$$ 33 ? ( G ) - 35 , where $$\omega (G)$$ ? ( G ) denotes the size of a maximum clique in $$G$$ G . Du et al. improved the upper bound to $$31\,\omega (G) - 1$$ 31 ? ( G ) - 1 . In this paper we decrease the bound substantially; namely we show that the chromatic number of $$G$$ G is at most $$15\,\omega (G) - 14$$ 15 ? ( G ) - 14 .
Databáze: OpenAIRE
Externí odkaz: