On the chromatic number of disjointness graphs of curves

Pach, János and Tomon, István (2020) On the chromatic number of disjointness graphs of curves. JOURNAL OF COMBINATORIAL THEORY SERIES B, 144. pp. 167-190. ISSN 0095-8956

[img] Text
Restricted to Repository staff only

Download (250kB) | Request a copy


Let ω(G) and χ(G) denote the clique number and chromatic number of a graph G, respectively. The disjointness graph of a family of curves (continuous arcs in the plane) is the graph whose vertices correspond to the curves and in which two vertices are joined by an edge if and only if the corresponding curves are disjoint. A curve is called x-monotone if every vertical line intersects it in at most one point. An x-monotone curve is grounded if its left endpoint lies on the y-axis. We prove that if G is the disjointness graph of a family of grounded x-monotone curves such that ω(G)=k, then χ(G)≤(k+12). If we only require that every curve is x-monotone and intersects the y-axis, then we have χ(G)≤[Formula presented](k+23). Both of these bounds are best possible. The construction showing the tightness of the last result settles a 25 years old problem: it yields that there exist Kk-free disjointness graphs of x-monotone curves such that any proper coloring of them uses at least Ω(k4) colors. This matches the upper bound up to a constant factor. © 2020 Elsevier Inc.

Item Type: Article
Uncontrolled Keywords: CURVES; Chromatic number; Intersection graph;
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Depositing User: MTMT SWORD
Date Deposited: 11 Mar 2021 14:47
Last Modified: 25 Apr 2023 09:28

Actions (login required)

Edit Item Edit Item