Search

We give a short proof of the chromatic e-positivity conjecture of Stanley for length-2 partitions., Comment: 11 pages. arXiv admin note: text overlap with arXiv:1702.05791

Conflict-free coloring (in short, CF-coloring) of a graph $G = (V,E)$ is a coloring of $V$ such that the neighborhood of each vertex contains a vertex whose color differs from the color of any other vertex in that neighborhood. Bounds on CF-chromatic numbers have been studied both for general graphs and for intersection graphs of geometric shapes. In this paper we obtain such bounds for several classes of string graphs, i.e., intersection graphs of curves in the plane: (i) We provide a general upper bound of $O(\chi(G)^2 \log n)$ on the CF-chromatic number of any string graph $G$ with $n$ vertices in terms of the classical chromatic number $\chi(G)$. This result stands in contrast to general graphs where the CF-chromatic number can be $\Omega(\sqrt{n})$ already for bipartite graphs. (ii) For some central classes of string graphs, the CF-chromatic number is as large as $\Theta(\sqrt{n})$, which is the upper bound for any graph even in the non-geometric context. For several such classes (e.g., intersection graphs of frames) we prove a tight bound of $\Theta(\log n)$ with respect to the notion of $k$-CF-coloring (in which the punctured neighborhood of each vertex contains a color that appears at most $k$ times), for a small constant $k$. (iii) We obtain a general upper bound on the $k$-CF-chromatic number of arbitrary hypergraphs: Any hypergraph with $m$ hyperedges can be $k$-CF colored with $\tilde{O}(m^{\frac{1}{k+1}})$ colors. This bound, which extends a bound of Pach and Tardos (2009), is tight for some string graphs, up to a logarithmic factor. (iv) Our fourth result concerns circle graphs in which coloring problems are motivated by VLSI designs. We prove a tight bound of $\Theta(\log n)$ on the CF-chromatic number of circle graphs, and an upper bound of $O(\log^{3} n)$ for a wider class that contains circle graphs, namely, intersection graphs of grounded L-shapes., Comment: 33 pages, 8 figures. A major extension of the previous version (that contained 19 pages), adding an upper bound on the CF-chromatic number of grounded L-shapes and other results

(i) We provide a short and simple proof of the first selection lemma. (ii) We also prove a selection lemma of a new type in $\Re^d$. For example, when $d=2$ assuming $n$ is large enough we prove that for any set $P$ of $n$ points in general position there are $\Omega(n^4)$ pairs of segments spanned by $P$ all of which intersect in some fixed triangle spanned by $P$. (iii) Finally, we extend the weak $\frac{1}{r}$-net theorem to a kinetic setting where the underlying set of points is moving polynomially with bounded description complexity. We establish that one can find a kinetic analog $N$ of a weak $\frac{1}{r}$-net of cardinality $O(r^{\frac{d(d+1)}{2}}\log^{d}r)$ whose points are moving with coordinates that are rational functions with bounded description complexity. Moreover, each member of $N$ has one polynomial coordinate.

We prove that for every integer $t\geq 1$, the class of intersection graphs of curves in the plane each of which crosses a fixed curve in at least one and at most $t$ points is $\chi$-bounded. This is essentially the strongest $\chi$-boundedness result one can get for this kind of graph classes. As a corollary, we prove that for any fixed integers $k\geq 2$ and $t\geq 1$, every $k$-quasi-planar topological graph on $n$ vertices with any two edges crossing at most $t$ times has $O(n\log n)$ edges., Comment: Small corrections, improved presentation

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., Comment: Introduction extended by a survey of results on (outer)string graphs, some minor corrections