Coloring intersection graphs of x-monotone curves in the plane
Coloring intersection graphs of \(x\)-monotone curves in the plane
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.
- Approximation schemes for covering and packing problems in image processing and VLSI
- Coloring k k -free intersection graphs of geometric objects in the plane
- Coloring relatives of intervals on the plane. I: Chromatic number versus girth
- Colouring arcwise connected sets in the plane. I
- Colouring arcwise connected sets in the plane. II
- Colouring relatives of intervals on the plane. II: Intervals and rays in two directions
- Covering and coloring polygon-circle graphs
- Covering and coloring problems for relatives of intervals
- Graph Theory and Probability
- scientific article; zbMATH DE number 1017008 (Why is no real title available?)
- Image encryption through the bit plane decomposition
- Intersection patterns of curves
- Label placement by maximum independent set in rectangles
- On a Coloring Problem.
- On bounding the chromatic number of L-graphs
- On the chromatic number of multiple interval graphs and overlap graphs
- The maximum number of unit distances in a convex n-gon
- Triangle-free intersection graphs of line segments with large chromatic number
- 3-coloring arrangements of line segments with 4 slopes is hard
- Conflict-free coloring of string graphs
- Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors
- Coloring curves that cross a fixed curve
- Triangle-free geometric intersection graphs with large chromatic number
- Triangle-free intersection graphs of line segments with large chromatic number
- scientific article; zbMATH DE number 1341210 (Why is no real title available?)
- Coloring curves that cross a fixed curve
- Outerstring graphs are \(\chi\)-bounded
- Coloring intersection graphs of arc-connected sets in the plane
- Twin-width II: small classes
- On the chromatic number of disjointness graphs of curves
- On the size of outer-string representations
- Box and Segment Intersection Graphs with Large Girth and Chromatic Number
- Outerstring graphs are -bounded
- Choice of the control variables of an isolated intersection by graph colouring
- Refining the hierarchies of classes of geometric intersection graphs
- Refining the hierarchies of classes of geometric intersection graphs
- Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
- Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded
- Proper colorability of segment intersection graphs
- Coloring triangle-free L-graphs with \(O (\log \log n)\) colors
- Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
- Proper colorability of segment intersection graphs
- Coloring triangle-free L-graphs with O( n) colors
- The -binding function of d-directional segment graphs
- 1-planar unit distance graphs
- Chromatic number of intersection graphs of segments with two slopes (extended abstract)
- On the chromatic number of disjointness graphs of curves
This page was built for publication: Coloring intersection graphs of \(x\)-monotone curves in the plane
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q485004)
