pith. sign in

arxiv: 1312.1678 · v3 · pith:3RIPXWB5new · submitted 2013-12-05 · 🧮 math.CO · cs.CG

Note on the number of edges in families with linear union-complexity

classification 🧮 math.CO cs.CG
keywords edgesfamilygraphintersectionlinearnumberomegaunion-complexity
0
0 comments X
read the original abstract

We give a simple argument showing that the number of edges in the intersection graph $G$ of a family of $n$ sets in the plane with a linear union-complexity is $O(\omega(G)n)$. In particular, we prove $\chi(G)\leq \text{col}(G)< 19\omega(G)$ for intersection graph $G$ of a family of pseudo-discs, which improves a previous bound.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.