edge clique cover number
tags: covering edges
equivalent to: edge clique cover number
Relations
Other | Relation from | Relation to |
---|---|---|
acyclic chromatic number | exclusion | exclusion |
arboricity | exclusion | exclusion |
average degree | exclusion | exclusion |
average distance | exclusion | upper bound |
bandwidth | exclusion | exclusion |
bipartite | unbounded | exclusion |
bipartite number | exclusion | upper bound |
bisection bandwidth | exclusion | exclusion |
block | unbounded | exclusion |
book thickness | exclusion | exclusion |
boolean width | exclusion | upper bound |
bounded components | unknown to HOPS | exclusion |
boxicity | exclusion | upper bound |
branch width | exclusion | exclusion |
c-closure | exclusion | exclusion |
carving-width | exclusion | exclusion |
chordal | unbounded | exclusion |
chordality | exclusion | upper bound |
chromatic number | exclusion | exclusion |
clique cover number | exclusion | exclusion |
clique-tree-width | exclusion | upper bound |
clique-width | exclusion | upper bound |
cluster | unknown to HOPS | exclusion |
co-cluster | unknown to HOPS | exclusion |
cograph | unknown to HOPS | exclusion |
complete | constant | exclusion |
connected | unbounded | unknown to HOPS |
cutwidth | exclusion | exclusion |
cycle | unbounded | exclusion |
cycles | unbounded | exclusion |
d-path-free | exclusion | exclusion |
degeneracy | exclusion | exclusion |
degree treewidth | exclusion | exclusion |
diameter | exclusion | upper bound |
diameter+max degree | unknown to HOPS | exclusion |
disjoint cycles | unbounded | exclusion |
distance to bipartite | exclusion | exclusion |
distance to block | exclusion | exclusion |
distance to bounded components | exclusion | exclusion |
distance to chordal | exclusion | exclusion |
distance to cluster | exclusion | exclusion |
distance to co-cluster | exclusion | exclusion |
distance to cograph | exclusion | exclusion |
distance to complete | upper bound | exclusion |
distance to edgeless | exclusion | exclusion |
distance to forest | exclusion | exclusion |
distance to interval | exclusion | exclusion |
distance to linear forest | exclusion | exclusion |
distance to maximum degree | exclusion | exclusion |
distance to outerplanar | exclusion | exclusion |
distance to perfect | exclusion | exclusion |
distance to planar | exclusion | unknown to HOPS |
distance to stars | exclusion | exclusion |
domatic number | exclusion | exclusion |
domination number | exclusion | exclusion |
edge connectivity | exclusion | exclusion |
edgeless | unknown to HOPS | exclusion |
feedback edge set | exclusion | exclusion |
feedback vertex set | exclusion | exclusion |
forest | unbounded | exclusion |
genus | exclusion | exclusion |
girth | exclusion | upper bound |
grid | unbounded | exclusion |
h-index | exclusion | exclusion |
inf-flip-width | exclusion | upper bound |
interval | unbounded | exclusion |
iterated type partitions | exclusion | upper bound |
linear clique-width | exclusion | upper bound |
linear forest | unbounded | exclusion |
linear NLC-width | exclusion | upper bound |
linear rank-width | exclusion | upper bound |
maximum clique | exclusion | exclusion |
maximum degree | exclusion | exclusion |
maximum independent set | exclusion | exclusion |
maximum induced matching | exclusion | unknown to HOPS |
maximum leaf number | exclusion | exclusion |
maximum matching | exclusion | exclusion |
maximum matching on bipartite graphs | unknown to HOPS | exclusion |
mim-width | exclusion | upper bound |
minimum degree | exclusion | exclusion |
mm-width | exclusion | exclusion |
modular-width | exclusion | upper bound |
module-width | exclusion | upper bound |
neighborhood diversity | exclusion | upper bound |
NLC-width | exclusion | upper bound |
NLCT-width | exclusion | upper bound |
odd cycle transversal | exclusion | exclusion |
outerplanar | unbounded | exclusion |
path | unbounded | exclusion |
pathwidth | exclusion | exclusion |
pathwidth+maxdegree | exclusion | exclusion |
perfect | unbounded | exclusion |
planar | unbounded | exclusion |
radius-r flip-width | exclusion | upper bound |
rank-width | exclusion | upper bound |
shrub-depth | exclusion | upper bound |
sim-width | exclusion | upper bound |
star | unknown to HOPS | exclusion |
stars | unknown to HOPS | exclusion |
topological bandwidth | exclusion | exclusion |
tree | unbounded | exclusion |
tree-independence number | exclusion | unknown to HOPS |
treedepth | exclusion | exclusion |
treelength | exclusion | upper bound |
treewidth | exclusion | exclusion |
twin-cover number | exclusion | exclusion |
twin-width | exclusion | upper bound |
vertex connectivity | unknown to HOPS | exclusion |
vertex cover | exclusion | exclusion |
vertex integrity | exclusion | exclusion |
Results
- 2022 Expanding the Graph Parameter Hierarchy by Tran
- 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 upper bounds neighborhood diversity by an exponential function – 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 upper bounds edge clique cover number by a polynomial function – 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 source
- edge clique cover number upper bounds neighborhood diversity by an exponential function – Label vertices by the cliques they are contained in, each label is its own group in the neighborhood diversity, connect accordingly.
- distance to complete upper bounds edge clique cover number by a polynomial function – 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.