vertex cover

• 2022/09 Tran2022
  • page 18 : vertex cover $k$ upper bounds twin-cover number by $\mathcal O(k)$ – 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 $k$ upper bounds neighborhood diversity by $2^{\mathcal O(k)}$ – 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 GanianTwinCover2012
  • 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.
• https://en.wikipedia.org/wiki/Vertex_cover
  • vertex cover – … set of vertices that includes at least one endpoint of every edge of the graph.
• unknown
  • maximum matching on bipartite graphs $k$ implies that vertex cover is $\mathcal O(k)$ – Kőnig’s theorem
  • vertex cover $k$ implies that maximum matching is $\mathcal O(k)$ – Every edge of the matching needs to be covered by at least one vertex. Path shows lower bound.
  • vertex cover $k$ upper bounds neighborhood diversity by $2^{\mathcal O(k)}$
  • vertex cover $k$ upper bounds twin-cover number by $\mathcal O(k)$ – By definition
  • vertex cover is equal to distance to edgeless
  • edgeless upper bounds vertex cover by a constant
• SchroderThesis
  • 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