Coloring intersection graphs of x-monotone curves in the plane
A class of graphs G is χ-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 families of x-monotone curves in the plane intersecting a vertical line is χ-bounded. As a corollary, we show that t...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer-Verlag
2016
|
| Online Access: | http://hdl.handle.net/1721.1/104885 |
| Summary: | A class of graphs G is χ-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 families of x-monotone curves in the plane intersecting a vertical line is χ-bounded. As a corollary, we show that the class of intersection graphs of rays in the plane is χ-bounded, and the class of intersection graphs of unit segments in the plane is χ-bounded. |
|---|