Coloring intersection graphs of arc-connected sets in the plane

DOI10.1007/s00454-014-9614-5zbMath1302.05041arXiv1310.7558OpenAlexW3099405462WikidataQ59399247 ScholiaQ59399247MaRDI QIDQ464743

Michał Lasoń, Arkadiusz Pawlik, Piotr Micek, Bartosz Walczak

Publication date: 29 October 2014

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numbergeometric intersection graphs\(\chi\)-boundedness

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (10)

3-coloring arrangements of line segments with 4 slopes is hard ⋮ Coloring curves that cross a fixed curve ⋮ Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded ⋮ 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 triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors ⋮ Conflict-free coloring of string graphs ⋮ Unnamed Item ⋮ On the chromatic number of disjointness graphs of curves ⋮ Outerstring Graphs are $\chi$-Bounded

Cites Work

• Unnamed Item
• Triangle-free geometric intersection graphs with large chromatic number
• Triangle-free intersection graphs of line segments with large chromatic number
• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
• Coloring intersection graphs of \(x\)-monotone curves in the plane
• On the chromatic number of multiple interval graphs and overlap graphs
• Covering and coloring polygon-circle graphs
• On the chromatic number of intersection graphs of convex sets in the plane
• On bounding the chromatic number of L-graphs
• A Separator Theorem for String Graphs and its Applications
• On a Coloring Problem.
• Outerstring graphs are χ-bounded
• Sur le coloriage des graphs
• Colouring arcwise connected sets in the plane. I
• Corrigendum

This page was built for publication: Coloring intersection graphs of arc-connected sets in the plane