Coloring translates and homothets of a convex body

2010/08/07 by Adrian Dumitrescu, Dumitrescu, Adrian, Minghui Jiang +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Metric Geometry (math.MG) #Point processes and geometric inequalities

paper · pdf · doi:10.48550/arxiv.1008.1360

openalex publication_date 2010/08/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We obtain improved upper bounds and new lower bounds on the chromatic number as a linear function of the clique number, for the intersection graphs (and their complements) of finite families of translates and homothets of a convex body in \RRⁿ.

Related

• Piercing translates and homothets of a convex body
• Homothetic Polygons and Beyond: Intersection Graphs, Recognition, and Maximum Clique
• Illuminating and covering convex bodies
• ?, ?, and ?
• On the convex hull and homothetic convex hull functions of a convex body