Affordable Access

Coloring intersection graphs of x-monotone curves in the plane

Authors
  • Suk, Andrew
Type
Preprint
Publication Date
Aug 26, 2013
Submission Date
Jan 04, 2012
Identifiers
arXiv ID: 1201.0887
Source
arXiv
License
Yellow
External links

Abstract

A class of graphs G is chi-bounded if the chromatic number of the graphs in G is bounded by some function of their clique number. We show that the class of intersection graphs of simple x-monotone curves in the plane intersecting a vertical line is chi-bounded. As a corollary we show that the class of intersection graphs of rays in the plane is chi-bounded, and the class of intersection graphs of unit segments in the plane is chi-bounded

Report this publication

Statistics

Seen <100 times