|
|||||
|
|
Note on coloring of double disk graphs |
|
| Authors: | Jaka Kranjc Borut Lu?ar Martina Mockov?iaková Roman Soták |
| Institution: | 1. Faculty of Information Studies, Novo mesto, Slovenia 2. Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia 3. European Centre of Excellence NTIS - New Technologies for the Information Society, Department of Mathematics, University of West Bohemia, Pilsen, Czech Republic 4. Institute of Mathematics, Faculty of Science, P. J. ?afárik University, Kosice, Slovakia |
| Abstract: | The coloring of disk graphs is motivated by the frequency assignment problem. In 1998, Malesińska et al. introduced double disk graphs as their generalization. They showed that the chromatic number of a double disk graph \(G\) is at most \(33\,\omega (G) - 35\) , where \(\omega (G)\) denotes the size of a maximum clique in \(G\) . Du et al. improved the upper bound to \(31\,\omega (G) - 1\) . In this paper we decrease the bound substantially; namely we show that the chromatic number of \(G\) is at most \(15\,\omega (G) - 14\) . |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |