Coloring translates and homothets of a convex body

DOI10.1007/S13366-011-0048-4MaRDI QIDQ695002zbMATH OpenOpenAlexFDO

Authors Adrian Dumitrescu, Minghui Jiang

Publication date 20 December 2012

Published in Beiträge zur Algebra und Geometrie (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.1360

zbMATH Keywords

graph coloringgeometric intersection graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

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 $R{R}^n$.

Recommendations

• A colorful theorem on transversal lines to plane convex sets
• The colored Hadwiger transversal theorem in \(\mathbb{R}^d\)
• Transversals, topology and colorful geometric results
• Coloring arcs of convex sets
• On colorings and isometries
• scientific article; zbMATH DE number 5519219
• Colourful transversal theorems
• Translative covering a convex body by its homothetic copies
• Covering convex bodies by translates of convex bodies
• Coloring \({\mathbb R}^n\)

Cites work

• scientific article; zbMATH DE number 2145236 (Why is no real title available?)
• scientific article; zbMATH DE number 3214278 (Why is no real title available?)
• A note on coverings
• Algorithmic graph theory and perfect graphs
• Bounds on the chromatic number of intersection graphs of sets in the plane
• Coloring the complements of intersection graphs of geometric figures
• Covering and coloring problems for relatives of intervals
• Intersection Graphs of Rectangles and Segments
• Intrinsic area
• On a Coloring Problem.
• On the chromatic number of intersection graphs of convex sets in the plane
• On the chromatic number of multiple interval graphs and overlap graphs
• Piercing translates and homothets of a convex body
• Research Problems in Discrete Geometry
• Some Intersection Properties of Convex Bodies
• Some combinatorial problems

Cited in

(6)

• On the chromatic number of intersection graphs of convex sets in the plane
• Natural Color Categories Are Convex Sets
• A colorful theorem on transversal lines to plane convex sets
• Coloring Euclidean spaces so that all translates of a given set are rainbow
• A view from above on \(\mathrm{JN}_p( \mathbb{R}^n)\)
• Flipping triangles and rectangles

This page was built for publication: Coloring translates and homothets of a convex body

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q695002)