interval

• 2017 Diestel2017
  • page 145 : interval – A graph $G$ is called an \emph{interval graph} if there exists a set ${ I_v \mid v \in V(G) }$ of real intervals such that $I_u \cap I_v \ne \emptyset$ if and only if $uv \in E(G)$.
• unknown
  • interval upper bounds distance to interval by a constant – by definition
  • graph class interval has unbounded average distance
• assumed
  • cluster upper bounds interval by a constant
  • graph class interval is not included in graph class cluster
  • linear forest upper bounds interval by a constant
  • graph class interval is not included in graph class linear forest
  • stars upper bounds interval by a constant
  • graph class interval is not included in graph class stars
  • interval upper bounds chordal by a constant
  • graph class chordal is not included in graph class interval