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. Triangle-Free Geometric Intersection Graphs with Large Chromatic Number
 
research article

Triangle-Free Geometric Intersection Graphs with Large Chromatic Number

Pawlik, Arkadiusz
•
Kozik, Jakub
•
Krawczyk, Tomasz
Show more
2013
Discrete & Computational Geometry

Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set in that is not an axis-aligned rectangle and for any positive integer produces a family of sets, each obtained by an independent horizontal and vertical scaling and translation of , such that no three sets in pairwise intersect and . This provides a negative answer to a question of Gyarfas and Lehel for L-shapes. With extra conditions we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries or equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.

  • Files
  • Details
  • Metrics
Type
research article
DOI
10.1007/s00454-013-9534-9
Web of Science ID

WOS:000324494500007

Author(s)
Pawlik, Arkadiusz
Kozik, Jakub
Krawczyk, Tomasz
Lason, Michal  
Micek, Piotr
Trotter, William T.
Walczak, Bartosz  
Date Issued

2013

Publisher

Springer US

Published in
Discrete & Computational Geometry
Volume

50

Issue

3

Start page

714

End page

726

Subjects

Intersection graph

•

Triangle-free

•

Chromatic number

•

On-line

Note

National Licences

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
November 4, 2013
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/96596
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