Skip to main content

New answers tagged

1 vote
Accepted

Bounds on lengths of boxes in bounded-degree box graphs

$\DeclareMathOperator{\cub}{\operatorname{cub}}$$\DeclareMathOperator{\box}{\operatorname{box}}$$\DeclareMathOperator{\diam}{\operatorname{diam}}$I now think that the answer to the second question is ...
Pranay Gorantla's user avatar
3 votes
Accepted

Bounds on lengths of intervals in bounded-degree interval graphs

Yes, we may take the function to be $2\Delta$. Lemma. Every interval graph $G$ has an interval representation where all intervals have length between $1$ and $2\Delta$, where $\Delta$ is the maximum ...
Tony Huynh's user avatar
  • 31.8k

Top 50 recent answers are included