Back to Search
Start Over
Note on coloring of double disk graphs.
- Source :
- Journal of Global Optimization; Dec2014, Vol. 60 Issue 4, p793-799, 7p
- Publication Year :
- 2014
-
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$$ . [ABSTRACT FROM AUTHOR]
- Subjects :
- CHROMATIC polynomial
GRAPH theory
ALGORITHMS
MATHEMATICS
GENERALIZATION
Subjects
Details
- Language :
- English
- ISSN :
- 09255001
- Volume :
- 60
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- Journal of Global Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 99391920
- Full Text :
- https://doi.org/10.1007/s10898-014-0221-z