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 |
| _version_ | 1826213640563326976 |
|---|---|
| author | Suk, Andrew |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Suk, Andrew |
| author_sort | Suk, Andrew |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T15:52:29Z |
| format | Article |
| id | mit-1721.1/104885 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:52:29Z |
| publishDate | 2016 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/1048852022-09-29T16:44:11Z Coloring intersection graphs of x-monotone curves in the plane Suk, Andrew Massachusetts Institute of Technology. Department of Mathematics Suk, Andrew 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. National Science Foundation (U.S.) (Postdoctoral Fellowship) 2016-10-20T18:30:12Z 2016-10-20T18:30:12Z 2014-06 2012-02 2016-08-18T15:28:17Z Article http://purl.org/eprint/type/JournalArticle 0209-9683 1439-6912 http://hdl.handle.net/1721.1/104885 Suk, Andrew. "Coloring intersection graphs of x-monotone curves in the plane." Combinatorica 34:4 (August 2014), pp. 487-505. en http://dx.doi.org/10.1007/s00493-014-2942-5 Combinatorica Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg application/pdf Springer-Verlag Springer Berlin Heidelberg |
| spellingShingle | Suk, Andrew Coloring intersection graphs of x-monotone curves in the plane |
| title | Coloring intersection graphs of x-monotone curves in the plane |
| title_full | Coloring intersection graphs of x-monotone curves in the plane |
| title_fullStr | Coloring intersection graphs of x-monotone curves in the plane |
| title_full_unstemmed | Coloring intersection graphs of x-monotone curves in the plane |
| title_short | Coloring intersection graphs of x-monotone curves in the plane |
| title_sort | coloring intersection graphs of x monotone curves in the plane |
| url | http://hdl.handle.net/1721.1/104885 |
| work_keys_str_mv | AT sukandrew coloringintersectiongraphsofxmonotonecurvesintheplane |