Coloring axis-parallel rectangles

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:117

Article

Pach, Janos^1,2,3  Tardos, Gabor⁴ 

[1] CUNY City Coll, New York, NY 10031 USA

[2] NYU, Courant Inst, New York, NY USA

[3] Ecole Polytech Fed Lausanne, CH-1015 Lausanne, Switzerland

[4] Simon Fraser Univ, Dept Comp Sci, Burnaby, BC V5A 1S6, Canada

关键词: Coloring;    Hypergraph;    Chromatic number;   

DOI  :  10.1016/j.jcta.2009.04.007

来源: Elsevier

【 摘 要 】

For every k and r, we construct a finite family of axis-parallel rectangles in the plane such that no matter how we color them with k colors, there exists a point covered by precisely r members of the family, all of which have the same color. For r = 2, this answers a question of S.. Smorodinsky [S. Smorodinsky, On the chromatic number of some geometric hypergraphs, SIAM J. Discrete Math. 21 (2007) 676-687]. (C) 2009 Elsevier Inc. All rights reserved.

【 授权许可】

Free