REAL

Coloring Kk-free intersection graphs of geometric objects in the plane

Fox, Jacob and Pach, János (2012) Coloring Kk-free intersection graphs of geometric objects in the plane. EUROPEAN JOURNAL OF COMBINATORICS, 33 (5). pp. 853-866. ISSN 0195-6698

[img]
Preview
Text
coloring030208.pdf

Download (234kB) | Preview

Abstract

The intersection graph of a collection C of sets is the graph on the vertex set C, in which C1,C2∈C are joined by an edge if and only if C 1∩C 2≠∅. Erdo s conjectured that the chromatic number of triangle-free intersection graphs of n segments in the plane is bounded from above by a constant. Here we show that it is bounded by a polylogarithmic function of n, which is the first nontrivial bound for this problem. More generally, we prove that for any t and k, the chromatic number of every K k-free intersection graph of n curves in the plane, every pair of which have at most t points in common, is at most (ctlognlogk)clogk, where c is an absolute constant and c t only depends on t. We establish analogous results for intersection graphs of convex sets, x-monotone curves, semialgebraic sets of constant description complexity, and sets that can be obtained as the union of a bounded number of sets homeomorphic to a disk.Using a mix of results on partially ordered sets and planar separators, for large k we improve the best known upper bound on the number of edges of a k-quasi-planar topological graph with n vertices, that is, a graph drawn in the plane with curvilinear edges, no k of which are pairwise crossing. As another application, we show that for every ε>0 and for every positive integer t, there exist δ>0 and a positive integer n 0 such that every topological graph with ngen 0 vertices, at least n 1+ε edges, and no pair of edges intersecting in more than t points, has at least n δ pairwise intersecting edges.

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 22 Nov 2019 08:32
Last Modified: 22 Nov 2019 08:32
URI: http://real.mtak.hu/id/eprint/103565

Actions (login required)

Edit Item Edit Item