Outerstring graphs are -bounded

DOI10.1145/2582112.2582115MaRDI QIDQ4635536zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

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
• scientific article; zbMATH DE number 7559254 (Why is no real title available?)
• 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
• On grounded -graphs and their relatives
• Refining the hierarchies of classes of geometric intersection graphs

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)