Coloring translates and homothets of a convex body

DOI10.1007/S13366-011-0048-4zbMATH Open1256.05070arXiv1008.1360OpenAlexW1981701231MaRDI QIDQ695002FDOQ695002

Minghui Jiang, Adrian Dumitrescu

Publication date: 20 December 2012

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

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$.

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

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
• Colourful transversal theorems
• Translative covering a convex body by its homothetic copies
• Covering convex bodies by translates of convex bodies
• Coloring \({\mathbb R}^n\)

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)

Cites Work

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

Cited In (5)

• 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
• 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)