distance to complete

• 2022/09 Tran2022
  • page 18 : bounded twin-cover number does not imply bounded distance to complete – Observation 3.3. Twin Cover Number is incomparable to Distance to Clique.
  • page 18 : bounded distance to complete does not imply bounded twin-cover number – Observation 3.3. Twin Cover Number is incomparable to Distance to Clique.
  • page 23 : distance to complete $k$ upper bounds edge clique cover number by $k^{\mathcal O(1)}$ – Proposition 4.2. Disatnce to Clique strictly upper bounds Edge Clique Cover Number.
  • page 23 : bounded edge clique cover number does not imply bounded distance to complete – Proposition 4.2. Disatnce to Clique strictly upper bounds Edge Clique Cover Number.
  • page 34 : bounded c-closure does not imply bounded distance to complete – Proposition 5.4. $c$-Closure is incomparable to Distance to Clique.
  • page 34 : bounded distance to complete does not imply bounded c-closure – Proposition 5.4. $c$-Closure is incomparable to Distance to Clique.
• unknown
  • complete upper bounds distance to complete by a constant – by definition
  • distance to complete $k$ upper bounds clique cover number by $\mathcal O(k)$ – We cover the $k$ vertices of the modulator by cliques of size $1$ and cover the remaining clique by another one.
  • distance to complete $k$ upper bounds edge clique cover number by $k^{\mathcal O(1)}$ – Cover the remaining clique, cover each modulator vertex and its neighborhood outside of it with another clique, cover each edge within the modulator by its own edge.
• SchroderThesis
  • page 16 : bounded distance to complete does not imply bounded maximum clique – Proposition 3.7
  • page 16 : bounded distance to complete does not imply bounded domatic number – Proposition 3.7
  • page 16 : bounded distance to complete does not imply bounded vertex connectivity – Proposition 3.8