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$$ 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 . |
Year | DOI | Venue |
---|---|---|
2014 | 10.1007/s10898-014-0221-z | Journal of Global Optimization |
Keywords | Field | DocType |
Disk graph,Double disk graph,Frequency assignment problem,Chromatic number | Frequency assignment problem,Discrete mathematics,Graph,Combinatorics,Clique,Chromatic scale,Upper and lower bounds,Omega,Mathematics | Journal |
Volume | Issue | ISSN |
60 | 4 | 0925-5001 |
Citations | PageRank | References |
0 | 0.34 | 14 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jaka Kranjc | 1 | 2 | 1.44 |
Borut Luzar | 2 | 42 | 10.86 |
Martina Mockovciaková | 3 | 19 | 5.04 |
Roman Soták | 4 | 128 | 24.06 |