Outerstring graphs are -bounded

DOI10.1145/2582112.2582115zbMATH Open1395.05063arXiv1312.1559OpenAlexW2118155424MaRDI QIDQ4635536FDOQ4635536

Authors: Alexandre Rok, Bartosz Walczak 

Publication date: 23 April 2018

Published in: Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

Abstract: An outerstring graph is an intersection graph of curves that lie in a common half-plane and have one endpoint on the boundary of that half-plane. We prove that the class of outerstring graphs is $chi$-bounded, which means that their chromatic number is bounded by a function of their clique number. This generalizes a series of previous results on $chi$-boundedness of outerstring graphs with various additional restrictions on the shape of curves or the number of times the pairs of curves can cross. The assumption that each curve has an endpoint on the boundary of the half-plane is justified by the known fact that triangle-free intersection graphs of straight-line segments can have arbitrarily large chromatic number.

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

Recommendations

• Outerstring graphs are \(\chi \)-bounded
• Coloring intersection graphs of \(x\)-monotone curves in the plane
• Bounds on the chromatic number of intersection graphs of sets in the plane
• Coloring curves that cross a fixed curve
• Coloring curves that cross a fixed curve

zbMATH Keywords

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (13)

• Coloring intersection graphs of arc-connected sets in the plane
• Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded
• On-line approach to off-line coloring problems on graphs with geometric representations
• Conflict-free coloring of string graphs
• Coloring curves that cross a fixed curve
• Title not available (Why is that?)
• On the size of outer-string representations
• On the chromatic number of disjointness graphs of curves
• Intersection graphs of rays and grounded segments
• Outerstring graphs are \(\chi \)-bounded
• Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
• Refining the hierarchies of classes of geometric intersection graphs
• On grounded \(\llcorner\)-graphs and their relatives

This page was built for publication: Outerstring graphs are \(\chi\)-bounded

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635536)