BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Marco Caoduro contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We prove that for any triangle-free intersection graph of $n$ axis-parallel segments in the plane, the independence number $α$ of this graph is at least $α\ge n/4 + Ω(\sqrt{n})$. We complement this with a construction of a graph in this class satisfying $α\le n/4 + c \sqrt{n}$ for an absolute constant $c$, which demonstrates the optimality of our result.
Let $\mathcal{R}$ be a family of axis-parallel rectangles in the plane. The transversal number $τ(\mathcal{R})$ is the minimum number of points needed to pierce all the rectangles. The independence number $ν(\mathcal{R})$ is the maximum number of pairwise disjoint rectangles. Given a positive real number $r$, we say that $\mathcal{R}$ is an r-bounded family if, for any rectangle in $\mathcal{R}$, the aspect ratio of the longer side over the shorter side is at most $r$. Gyárfás and Lehel asked if it is possible to bound the transversal number $τ(\mathcal{R})$ with a linear function of the independence number $ν(\mathcal{R})$. Ahlswede and Karapetyan claimed a positive answer for the particular case of $r$-bounded families, but without providing proof. Chudnovsky et al. confirmed the result proving the bound $τ\leq (14 + 2r^2) ν$. This note aims at giving a simple proof of $τ\leq 2(r+1)(ν-1) + 1$, slightly improving the previous results. As a consequence of this new approach, we also deduce a constant factor bound for the ratio $\fracχω$ in the case of $r$-bounded family.