Coloring intersection graphs of \(x\)-monotone curves in the plane (Q485004): Difference between revisions

Classes of graphs, in which the chromatic number is bounded by a function of the clique number have been investigated for long, as a relaxation of perfect graphs. They are called \(\chi\)-bounded classes. A family of curves is called simple, if every pair of them intersects at most once, and if two curves have a point in common, then they cross each other at that point. The paper shows that the class of intersection graphs of simple families of \(x\)-monotone curves in the plane, such that each crosses a fixed vertical line, is \(\chi\)-bounded. The vertical line condition cannot be dropped, while the necessity of simple curves is unclear.