edge clique cover number

• 2022/09 Tran2022
  • page 14 : edge clique cover number – The edge clique cover number $eccn(G)$ of a graph $G$ is the minimum number of complete subgraphs required such that each edge is contained in at least one of them.
  • page 22 : edge clique cover number $k$ upper bounds neighborhood diversity by $2^{\mathcal O(k)}$ – Theorem 4.1. Edge Clique Cover Number strictly upper bounds Neighborhood Diversity.
  • page 22 : bounded neighborhood diversity does not imply bounded edge clique cover number – Theorem 4.1. Edge Clique Cover Number strictly upper bounds Neighborhood Diversity.
  • 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 29 : bounded edge clique cover number does not imply bounded vertex cover – Proposition 4.13. Edge Clique Cover Number is incomparable to Vertex Cover Number.
  • page 29 : bounded vertex cover does not imply bounded edge clique cover number – Proposition 4.13. Edge Clique Cover Number is incomparable to Vertex Cover Number.
  • page 29 : bounded edge clique cover number does not imply bounded domination number – Proposition 4.14. Edge Clique Cover Number is incomparable to Domination Number.
  • page 29 : bounded domination number does not imply bounded edge clique cover number – Proposition 4.14. Edge Clique Cover Number is incomparable to Domination Number.
  • page 29 : bounded edge clique cover number does not imply bounded distance to perfect – Proposition 4.15. Edge Clique Cover Number is incomparable to Distance to Perfect.
  • page 29 : bounded distance to perfect does not imply bounded edge clique cover number – Proposition 4.15. Edge Clique Cover Number is incomparable to Distance to Perfect.
• unknown
  • edge clique cover number $k$ upper bounds neighborhood diversity by $2^{\mathcal O(k)}$ – Label vertices by the cliques they are contained in, each label is its own group in the neighborhood diversity, connect accordingly.
  • 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.