edge clique cover number
- 2022/09 Tran2022
- page 15 : 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 23 : edge clique cover number $k$ upper bounds neighborhood diversity by $\mathcal O(k)$ – Theorem 4.1. Edge Clique Cover Number strictly upper bounds Neighborhood Diversity.
- page 23 : bounded neighborhood diversity does not imply bounded edge clique cover number – Theorem 4.1. Edge Clique Cover Number strictly upper bounds Neighborhood Diversity.
- page 24 : distance to complete $k$ upper bounds edge clique cover number by $\mathcal O(k)$ – Proposition 4.2. Disatnce to Clique strictly upper bounds Edge Clique Cover Number.
- page 24 : 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.
- 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.