vertex cover
abbr: vc
tags: vertex removal
equivalent to: vertex cover, distance to edgeless
Relations
Other | Relation from | Relation to |
---|---|---|
acyclic chromatic number | exclusion | upper bound |
arboricity | exclusion | upper bound |
average degree | exclusion | upper bound |
average distance | exclusion | upper bound |
bandwidth | exclusion | exclusion |
bipartite | unbounded | unknown to HOPS |
bipartite number | exclusion | upper bound |
bisection bandwidth | exclusion | exclusion |
block | unbounded | unknown to HOPS |
book thickness | exclusion | upper bound |
boolean width | exclusion | upper bound |
bounded components | exclusion | exclusion |
boxicity | exclusion | upper bound |
branch width | exclusion | upper bound |
c-closure | exclusion | exclusion |
carving-width | exclusion | exclusion |
chordal | unbounded | unknown to HOPS |
chordality | exclusion | upper bound |
chromatic number | exclusion | upper bound |
clique cover number | exclusion | exclusion |
clique-tree-width | exclusion | upper bound |
clique-width | exclusion | upper bound |
cluster | unbounded | unknown to HOPS |
co-cluster | unbounded | unknown to HOPS |
cograph | unbounded | unknown to HOPS |
complete | unbounded | exclusion |
connected | unbounded | unknown to HOPS |
cutwidth | exclusion | exclusion |
cycle | unbounded | exclusion |
cycles | unbounded | exclusion |
d-path-free | exclusion | upper bound |
degeneracy | exclusion | upper bound |
degree treewidth | exclusion | exclusion |
diameter | exclusion | upper bound |
diameter+max degree | exclusion | exclusion |
disjoint cycles | unbounded | exclusion |
distance to bipartite | exclusion | upper bound |
distance to block | exclusion | upper bound |
distance to bounded components | exclusion | upper bound |
distance to chordal | exclusion | upper bound |
distance to cluster | exclusion | upper bound |
distance to co-cluster | exclusion | upper bound |
distance to cograph | exclusion | upper bound |
distance to complete | exclusion | exclusion |
distance to edgeless | equal | equal |
distance to forest | exclusion | upper bound |
distance to interval | exclusion | upper bound |
distance to linear forest | exclusion | upper bound |
distance to maximum degree | exclusion | upper bound |
distance to outerplanar | exclusion | upper bound |
distance to perfect | exclusion | upper bound |
distance to planar | exclusion | upper bound |
distance to stars | exclusion | upper bound |
domatic number | exclusion | upper bound |
domination number | exclusion | exclusion |
edge clique cover number | exclusion | exclusion |
edge connectivity | exclusion | upper bound |
edgeless | constant | exclusion |
feedback edge set | exclusion | exclusion |
feedback vertex set | exclusion | upper bound |
forest | unbounded | exclusion |
genus | exclusion | exclusion |
girth | exclusion | upper bound |
grid | unbounded | exclusion |
h-index | exclusion | upper bound |
inf-flip-width | exclusion | upper bound |
interval | unbounded | unknown to HOPS |
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 | upper bound |
maximum degree | exclusion | exclusion |
maximum independent set | exclusion | exclusion |
maximum induced matching | exclusion | upper bound |
maximum leaf number | exclusion | exclusion |
maximum matching | unknown to HOPS | tight bounds |
maximum matching on bipartite graphs | tight bounds | unknown to HOPS |
mim-width | exclusion | upper bound |
minimum degree | exclusion | upper bound |
mm-width | exclusion | upper bound |
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 | upper bound |
outerplanar | unbounded | exclusion |
path | unbounded | exclusion |
pathwidth | exclusion | upper bound |
pathwidth+maxdegree | exclusion | exclusion |
perfect | unbounded | unknown to HOPS |
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 | constant | exclusion |
stars | unbounded | exclusion |
topological bandwidth | exclusion | exclusion |
tree | unbounded | exclusion |
tree-independence number | exclusion | upper bound |
treedepth | exclusion | upper bound |
treelength | exclusion | upper bound |
treewidth | exclusion | upper bound |
twin-cover number | exclusion | upper bound |
twin-width | exclusion | upper bound |
vertex connectivity | unknown to HOPS | unknown to HOPS |
vertex integrity | exclusion | upper bound |
Results
- 2022 Expanding the Graph Parameter Hierarchy by Tran
- page 18 : vertex cover upper bounds twin-cover number by a linear function – By definition
- page 18 : graph class complete has unbounded vertex cover – Note that a clique of size $n$ has … a vertex cover number of $n-1$
- page 23 : vertex cover upper bounds neighborhood diversity by an exponential function – Proposition 4.3. Vertex Cover Number strictly upper bounds Neighborhood Diversity.
- page 23 : bounded neighborhood diversity does not imply bounded vertex cover – Proposition 4.3. Vertex Cover Number strictly upper bounds Neighborhood Diversity.
- 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 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.
- 2012 Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics by Ganian
- page 263 : bounded twin-cover number does not imply bounded vertex cover – The vertex cover of graphs of bounded twin-cover may be arbitrarily large.
- assumed
- vertex cover upper bounds twin-cover number by a linear function – By definition
- https://en.wikipedia.org/wiki/Vertex_cover
- vertex cover – … set of vertices that includes at least one endpoint of every edge of the graph.
- Comparing Graph Parameters by Schröder
- page 15 : bounded vertex cover does not imply bounded domination number – Proposition 3.5
- page 24 : bounded vertex cover does not imply bounded genus – Proposition 3.18
- page 24 : bounded vertex cover does not imply bounded maximum degree – Proposition 3.19
- page 24 : bounded vertex cover does not imply bounded bisection bandwidth – Proposition 3.20
- unknown source
- maximum matching on bipartite graphs upper and lower bounds vertex cover by a linear function – Kőnig’s theorem
- vertex cover upper and lower bounds maximum matching by a linear function – Every edge of the matching needs to be covered by at least one vertex. Path shows lower bound.
- vertex cover upper bounds neighborhood diversity by an exponential function
- vertex cover is equivalent to distance to edgeless
- distance to edgeless is equivalent to vertex cover
- graph class edgeless has constant vertex cover
- graph class star has constant vertex cover – trivially