Coloring intersection graphs of \(x\)-monotone curves in the plane

DOI10.1007/s00493-014-2942-5zbMath1340.05081arXiv1201.0887OpenAlexW2012767915MaRDI QIDQ485004

Andrew Suk

Publication date: 8 January 2015

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1201.0887

zbMATH Keywords

chromatic numberclique number\(x\)-monotone curveintersection graph of curves

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items

Twin-width II: small classes ⋮ 3-coloring arrangements of line segments with 4 slopes is hard ⋮ Triangle-free geometric intersection graphs with large chromatic number ⋮ Coloring curves that cross a fixed curve ⋮ Triangle-free intersection graphs of line segments with large chromatic number ⋮ 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 ⋮ New bounds on the maximum number of edges in \(k\)-quasi-planar graphs ⋮ Coloring intersection graphs of arc-connected sets in the plane ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ Box and Segment Intersection Graphs with Large Girth and Chromatic Number ⋮ Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors ⋮ Conflict-free coloring of string graphs ⋮ Unnamed Item ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ Unnamed Item ⋮ On the chromatic number of disjointness graphs of curves ⋮ Outerstring Graphs are $\chi$-Bounded

Cites Work

• Unnamed Item
• Unnamed Item
• Triangle-free intersection graphs of line segments with large chromatic number
• On the chromatic number of multiple interval graphs and overlap graphs
• Covering and coloring problems for relatives of intervals
• Label placement by maximum independent set in rectangles
• Colouring relatives of intervals on the plane. II: Intervals and rays in two directions
• Covering and coloring polygon-circle graphs
• Coloring relatives of intervals on the plane. I: Chromatic number versus girth
• The maximum number of unit distances in a convex \(n\)-gon
• On bounding the chromatic number of L-graphs
• Graph Theory and Probability
• On a Coloring Problem.
• Coloring k _k -free intersection graphs of geometric objects in the plane
• Approximation schemes for covering and packing problems in image processing and VLSI
• Intersection patterns of curves
• Colouring arcwise connected sets in the plane. I
• Colouring arcwise connected sets in the plane. II