Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Coloring K-k-free intersection graphs of geometric objects in the plane
 
research article

Coloring K-k-free intersection graphs of geometric objects in the plane

Fox, Jacob
•
Pach, Janos  
2012
European Journal Of Combinatorics

The intersection graph of a collection C of sets is the graph on the vertex set C, in which C-1 . C-2 is an element of C are joined by an edge if and only if C-1 boolean AND C-2 not equal empty set. Erdos conjectured that the chromatic number of triangle-free intersection graphs of n segments in the plane is bounded from above by a constant. Here we show that it is bounded by a polylogarithmic function of n, which is the first nontrivial bound for this problem. More generally, we prove that for any t and k, the chromatic number of every K-k-free intersection graph of n curves in the plane, every pair of which have at most t points in common, is at most (c(t) log n/log k)(c log k), where c is an absolute constant and c(t) only depends on t. We establish analogous results for intersection graphs of convex sets, x-monotone curves, semialgebraic sets of constant description complexity, and sets that can be obtained as the union of a bounded number of sets homeomorphic to a disk.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.ejc.2011.09.021
Web of Science ID

WOS:000301306200012

Author(s)
Fox, Jacob
Pach, Janos  
Date Issued

2012

Published in
European Journal Of Combinatorics
Volume

33

Start page

853

End page

866

Subjects

Approximation Algorithms

•

Separator Theorem

•

Packing Problems

•

Independent Set

•

Crossing Number

•

Convex-Sets

•

Rectangles

•

Relatives

•

Intervals

•

Patterns

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
April 5, 2012
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/79215
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés