c-closure
equivalent to: c-closure
Relations
Other | Relation from | Relation to |
---|---|---|
acyclic chromatic number | exclusion | exclusion |
arboricity | exclusion | exclusion |
average degree | exclusion | exclusion |
average distance | exclusion | exclusion |
bandwidth | upper bound | exclusion |
bipartite | unknown to HOPS | exclusion |
bipartite number | exclusion | unknown to HOPS |
bisection bandwidth | exclusion | exclusion |
block | unknown to HOPS | exclusion |
book thickness | exclusion | exclusion |
boolean width | exclusion | exclusion |
bounded components | upper bound | exclusion |
boxicity | exclusion | exclusion |
branch width | exclusion | exclusion |
carving-width | upper bound | exclusion |
chordal | unknown to HOPS | exclusion |
chordality | exclusion | unknown to HOPS |
chromatic number | exclusion | exclusion |
clique cover number | exclusion | exclusion |
clique-tree-width | exclusion | exclusion |
clique-width | exclusion | exclusion |
cluster | unknown to HOPS | exclusion |
co-cluster | unknown to HOPS | exclusion |
cograph | unknown to HOPS | exclusion |
complete | unknown to HOPS | exclusion |
connected | unknown to HOPS | unknown to HOPS |
cutwidth | upper bound | exclusion |
cycle | constant | exclusion |
cycles | constant | exclusion |
d-path-free | exclusion | exclusion |
degeneracy | exclusion | exclusion |
degree treewidth | upper bound | exclusion |
diameter | exclusion | exclusion |
diameter+max degree | upper bound | exclusion |
disjoint cycles | unknown to HOPS | 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 | exclusion | 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 | exclusion |
distance to stars | exclusion | exclusion |
domatic number | exclusion | exclusion |
domination number | exclusion | exclusion |
edge clique cover number | exclusion | exclusion |
edge connectivity | exclusion | unknown to HOPS |
edgeless | constant | exclusion |
feedback edge set | upper bound | exclusion |
feedback vertex set | exclusion | exclusion |
forest | constant | exclusion |
genus | exclusion | exclusion |
girth | exclusion | exclusion |
grid | constant | exclusion |
h-index | exclusion | exclusion |
inf-flip-width | exclusion | exclusion |
interval | unknown to HOPS | exclusion |
iterated type partitions | exclusion | exclusion |
linear clique-width | exclusion | exclusion |
linear forest | constant | exclusion |
linear NLC-width | exclusion | exclusion |
linear rank-width | exclusion | exclusion |
maximum clique | exclusion | exclusion |
maximum degree | upper bound | exclusion |
maximum independent set | exclusion | exclusion |
maximum induced matching | exclusion | exclusion |
maximum leaf number | upper bound | exclusion |
maximum matching | exclusion | exclusion |
maximum matching on bipartite graphs | unknown to HOPS | exclusion |
mim-width | exclusion | unknown to HOPS |
minimum degree | exclusion | exclusion |
mm-width | exclusion | exclusion |
modular-width | exclusion | exclusion |
module-width | exclusion | exclusion |
neighborhood diversity | exclusion | exclusion |
NLC-width | exclusion | exclusion |
NLCT-width | exclusion | exclusion |
odd cycle transversal | exclusion | exclusion |
outerplanar | unknown to HOPS | exclusion |
path | constant | exclusion |
pathwidth | exclusion | exclusion |
pathwidth+maxdegree | upper bound | exclusion |
perfect | unknown to HOPS | exclusion |
planar | unknown to HOPS | exclusion |
radius-r flip-width | exclusion | unknown to HOPS |
rank-width | exclusion | exclusion |
shrub-depth | exclusion | exclusion |
sim-width | exclusion | unknown to HOPS |
star | constant | exclusion |
stars | constant | exclusion |
topological bandwidth | unknown to HOPS | exclusion |
tree | constant | exclusion |
tree-independence number | exclusion | unknown to HOPS |
treedepth | exclusion | exclusion |
treelength | exclusion | unknown to HOPS |
treewidth | exclusion | exclusion |
twin-cover number | exclusion | exclusion |
twin-width | exclusion | exclusion |
vertex connectivity | exclusion | exclusion |
vertex cover | exclusion | exclusion |
vertex integrity | exclusion | exclusion |
Results
- 2022 Expanding the Graph Parameter Hierarchy by Tran
- page 14 : c-closure – The c-closure $\mathrm{cc}(G)$ of a graph $G$ is the smallest number $c$ such that any pair of vertices $v,w \in V(G)$ with $|N_G(v) \cap N_G(w)| \ge c$ is adjacent. …
- page 32 : maximum degree upper bounds c-closure by a linear function – Proposition 5.1. Maximum Degree strictly upper bounds $c$-Closure.
- page 32 : bounded c-closure does not imply bounded maximum degree – Proposition 5.1. Maximum Degree strictly upper bounds $c$-Closure.
- page 32 : feedback edge set upper bounds c-closure by a linear function – Theorem 5.2. Feedback Edge Number strictly upper bounds $c$-Closure.
- page 32 : bounded c-closure does not imply bounded feedback edge set – Theorem 5.2. Feedback Edge Number strictly upper bounds $c$-Closure.
- page 34 : bounded c-closure does not imply bounded vertex cover – Proposition 5.3. $c$-Closure is incomparable to Vertex Cover Number.
- page 34 : bounded vertex cover does not imply bounded c-closure – Proposition 5.3. $c$-Closure is incomparable to Vertex 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.
- page 34 : bounded c-closure does not imply bounded bisection bandwidth – Proposition 5.5. $c$-Closure is incomparable to Bisection Width.
- page 34 : bounded bisection bandwidth does not imply bounded c-closure – Proposition 5.5. $c$-Closure is incomparable to Bisection Width.
- page 34 : bounded c-closure does not imply bounded genus – Proposition 5.6. $c$-Closure is incomparable to Genus.
- page 34 : bounded genus does not imply bounded c-closure – Proposition 5.6. $c$-Closure is incomparable to Genus.
- page 34 : bounded c-closure does not imply bounded vertex connectivity – Observation 5.7. $c$-Closure is incomparable to Distance to Disconnected, Domatic Number and Maximum Clique.
- page 34 : bounded vertex connectivity does not imply bounded c-closure – Observation 5.7. $c$-Closure is incomparable to Distance to Disconnected, Domatic Number and Maximum Clique.
- page 34 : bounded c-closure does not imply bounded domatic number – Observation 5.7. $c$-Closure is incomparable to Distance to Disconnected, Domatic Number and Maximum Clique.
- page 34 : bounded domatic number does not imply bounded c-closure – Observation 5.7. $c$-Closure is incomparable to Distance to Disconnected, Domatic Number and Maximum Clique.
- page 34 : bounded c-closure does not imply bounded maximum clique – Observation 5.7. $c$-Closure is incomparable to Distance to Disconnected, Domatic Number and Maximum Clique.
- page 34 : bounded maximum clique does not imply bounded c-closure – Observation 5.7. $c$-Closure is incomparable to Distance to Disconnected, Domatic Number and Maximum Clique.
- page 35 : bounded c-closure does not imply bounded boxicity – Proposition 5.8. $c$-Closure is incomparable to Boxicity.
- page 35 : bounded boxicity does not imply bounded c-closure – Proposition 5.8. $c$-Closure is incomparable to Boxicity.
- unknown source
- maximum degree upper bounds c-closure by a computable function
- feedback edge set upper bounds c-closure by a computable function