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

Piotr Micek, Rom Pinchasi

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.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment