vertex cover
abbr: vc
tags: vertex removal
equivalent to: distance to edgeless, maximum matching
Definition: The minimum number of vertices that have to be removed to get an independent set.
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 | exclusion |
bipartite number | ■ | exclusion | upper bound |
bisection bandwidth | ■ | exclusion | exclusion |
block | ■ | unbounded | exclusion |
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 | exclusion |
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 | exclusion |
co-cluster | ■ | unbounded | exclusion |
cograph | ■ | unbounded | exclusion |
complete | ■ | unbounded | exclusion |
connected | ■ | unbounded | exclusion |
contraction complexity | ■ | exclusion | exclusion |
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 |
disconnected | ■ | unknown to HOPS | unknown to HOPS |
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 disconnected | ■ | exclusion | upper bound |
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 | ■ | upper bound | 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 | 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 | upper bound |
maximum degree | ■ | exclusion | exclusion |
maximum independent set | ■ | exclusion | exclusion |
maximum induced matching | ■ | exclusion | upper bound |
maximum leaf number | ■ | exclusion | exclusion |
maximum matching | ■ | upper bound | tight bounds |
maximum matching on bipartite graphs | ■ | tight bounds | exclusion |
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 | 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 |
size | ■ | upper bound | exclusion |
star | ■ | upper bound | 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 | ■ | exclusion | upper bound |
vertex cover | ■ | equal | equal |
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
- size upper bounds vertex cover by a linear function – By definition
- vertex cover is equivalent to vertex cover – assumed
- 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 that this relation is not better than linear.
- maximum matching upper bounds vertex cover by a linear function – A set of all vertices taking part in a maximum matching creates a vertex cover, hence $vc(G) \le 2 \cdot mm(G)$.
- 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
- edgeless upper bounds vertex cover by a constant
- star upper bounds vertex cover by a constant – trivially
- 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